package com.example.algorithm.service.impl;

import com.example.algorithm.model.UnionFindSet;
import com.example.algorithm.model.ZipStr;
import com.example.algorithm.service.OdService;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

/**
 * @author Administrator
 * @date 2025/6/3 16:26
 * @description
 */
public class OdServiceImpl  implements OdService {

    /**
     * NO.1 判断一组不等式是否满足约束并输出
     *
     * 给定一组不等式，判断是否成立并输出不等式的最大差(输出浮点数的整数部分)
     *
     * 要求:
     *
     * 不等式系数为 double类型，是一个二维数组
     * 不等式的变量为 int类型，是一维数组;
     * 不等式的目标值为 double类型，是一维数组
     * 不等式约束为字符串数组，只能是:“>”,“>=”,“<”,“<=”,“=”，
     *
     * @param arg
     */
    @Override
    public void inequality(String[] arg) {
        Scanner sc = new Scanner(System.in);
        //接收数组
        String [][] arr = Arrays.stream(sc.nextLine().split(";")).map(s->s.split(",")).toArray(String[][]::new);
        /**
         * 不等式系数
         */
        double[] a1 = Arrays.stream(arr[0]).mapToDouble(Double::parseDouble).toArray();
        double[] a2 = Arrays.stream(arr[1]).mapToDouble(Double::parseDouble).toArray();
        double[] a3 = Arrays.stream(arr[2]).mapToDouble(Double::parseDouble).toArray();
        /**
         * 不等式变量
         */
        double[] x = Arrays.stream(arr[3]).mapToDouble(Double::parseDouble).toArray();
        /**
         * 不等式目标值
         */
        double[] b = Arrays.stream(arr[4]).mapToDouble(Double::parseDouble).toArray();

        /**
         * 不等式约束(字符串类型)，比较符号
         */
        String[] y = arr[5];

        double diff1=a1[0]*x[0]+a1[1]*x[1]+a1[2]*x[2]+a1[3]*x[3]+a1[4]*x[4]-b[0];
        double diff2=a2[0]*x[0]+a2[1]*x[1]+a2[2]*x[2]+a2[3]*x[3]+a2[4]*x[4]-b[1];
        double diff3=a3[0]*x[0]+a3[1]*x[1]+a3[2]*x[2]+a3[3]*x[3]+a3[4]*x[4]-b[2];
        boolean result = compare(diff1,y[0])&&compare(diff2,y[1])&&compare(diff3,y[2]);
        double maxDiff = Math.max(Math.max(diff1,diff2),diff3);
        System.out.println(result+" "+(int)maxDiff);
    }



    /**
     * 符号比较
     * @param val
     * @param cons
     * @return
     */
    public boolean  compare(double val ,String cons){
        boolean result = false;
        switch (cons){
            case ">":
                result = val>0;
                break;
            case "<":
                result = val<0;
                break;
            case ">=":
                result = val>=0;
                break;
            case "<=":
                result = val<=0;
                break;
            case "=":
                result = val==0;
                break;
        }
        return result;

    }

    /**
     *  NO.2  返回矩阵中非1的元素个数
     *
     *存在一个m*n的二维数组，其成员取值范围为0，1，2。
     *
     * 其中值为1的元素具备同化特性，每经过1S，将上下左右值为0的元素同化为1。
     *
     * 而值为2的元素，免疫同化。
     *
     * 将数组所有成员随机初始化为0或2，再将矩阵的[0, 0]元素修改成1，在经过足够长的时间后求矩阵中有多少个元素是0或2（即0和2数量之和）。
     *
     * 输入描述
     * 输入的前两个数字是矩阵大小。后面是数字矩阵内容。
     *
     * 输出描述
     * 返回矩阵中非1的元素个数。
     *
     * @param arg
     */

    @Override
    public void nonOneMartrix(String[] arg) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int [][] matrix = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                matrix[i][j]=scanner.nextInt();
            }
        }
        matrix[0][0]=1;
        System.out.println(getResult(m,n,matrix));
    }



    /**
     * 获取结果
     * @param m
     * @param n
     * @param matrix
     */
    private  int getResult(int m ,int n,int [][]matrix){
        // 上、下、左、右偏移量
        int [][] offsets={{-1,0},{1,0},{0,-1},{0,1}};
        // 广搜队列
        LinkedList<int[]> queue= new LinkedList<>();

        queue.add(new int[]{0,0});

        int count=1;
        while (queue.size()>0){
            int[] pos = queue.removeFirst();
            int x = pos[0];
            int y = pos[1];
            for(int [] offset:offsets){
                int newX= x+offset[0];
                int newY= y+offset[1];
                if(newX>=0&&newX<m&&newY>=0&&newY<n&&matrix[newX][newY]==0){
                    matrix[newX][newY]=1;
                    count++;
                    queue.add(new int[]{newX,newY});
                }


            }


        }

        return m*n-count;

    }

    /**
     * NO. 3数目 补种
     * 题目描述
     * 近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。
     *
     * 一个月后，有M棵胡杨未能成活。
     *
     * 现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？
     *
     * 输入描述
     * N 总种植数量，1 <= N <= 100000
     *
     * M 未成活胡杨数量，M 个空格分隔的数，按编号从小到大排列，1 <= M <= N
     *
     * K 最多可以补种的数量，0 <= K <= M
     *
     *
     *
     *
     *
     * @param args
     */
    @Override
    public void replantingTree(String[] args) {
        // 创建一个扫描器对象，用于读取输入
        Scanner scanner = new Scanner(System.in);
        // 读取总共的胡杨树数量
        int total = scanner.nextInt();
        // 读取未成活的胡杨树数量
        int deadTotal = scanner.nextInt();
        // 创建一个数组来表示每棵树是否成活，0表示成活，1表示未成活
        int [] nums=new int[total];
        // 初始化数组，所有元素设为0，表示所有树最初都是成活的
        Arrays.fill(nums,0);
        // 根据输入，将未成活的树的位置标记为1
        for(int i=0;i<deadTotal;i++)
        {
            int num = scanner.nextInt();
            nums[num-1]=1;

        }
        // 读取可以补种的树的数量
        int supply= scanner.nextInt();
        // 初始化滑动窗口的左右边界
        int left=0;
        // 用于存储最大连续成活区域的长度
        int maxLen=0;
        // 滑动窗口左边界的未成活树数量
        int sumLeft=0;
        // 滑动窗口右边界的未成活树数量
        int sumRight=0;
        // 遍历所有的树，right代表滑动窗口的右边界
        for(int right=0;right<total;right++){
            // 更新右边界的未成活树数量
            sumRight+=nums[right];
            // 如果窗口内的未成活树数量大于可以补种的数量
            while (sumLeft-sumRight>supply){
                sumLeft+=nums[left];
                // 缩小窗口，左边界右移
                left++;
            }
            maxLen=Math.max(maxLen,right-left+1);
        }

        System.out.println(maxLen);

    }



    /**
     * NO.4 传递悄悄话
     * 给定一个二叉树，每个节点上站一个人，节点数字表示父节点到该节点传递悄悄话需要花费的时间。
     *
     * 初始时，根节点所在位置的人有一个悄悄话想要传递给其他人，求二叉树所有节点上的人都接收到悄悄话花费的时间。
     *
     * @param args
     */

    @Override
    public void whispers(String[] args) {
        // 创建一个扫描器对象，用于读取输入
        Scanner scanner = new Scanner(System.in);
        int[] times = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        scanner.close();
        int maxTime=0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        while (!queue.isEmpty()){
            int index = queue.poll();
            int leftIndex=index*2+1;
            int rightIndex=index*2+2;
            if(leftIndex<times.length&&times[leftIndex]!=-1){
                times[leftIndex]+=times[index];
                queue.add(leftIndex);
                maxTime=Math.max(maxTime,times[leftIndex]);
            }

            if(rightIndex<times.length&&times[rightIndex]!=-1){
                times[rightIndex]+=times[index];
                queue.add(rightIndex);
                maxTime=Math.max(maxTime,times[rightIndex]);
            }

        }
        System.out.println(maxTime);
    }


    /**
     * NO.5 分披萨
     *
     * "吃货"和"馋嘴"两人到披萨店点了一份铁盘（圆形）披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。
     *
     * 由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从"吃货"开始，轮流取披萨。除了第一块披萨可以任意选取外，其他都必须从缺口开始选。
     *
     * 他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货"知道"馋嘴"的想法。
     *
     * 已知披萨小块的数量以及每块的大小，求"吃货"能分得的最大的披萨大小的总和。
     *
     * 输入描述
     * 第 1 行为一个正整数奇数 N，表示披萨小块数量。
     *
     * 3 ≤ N < 500
     * 接下来的第 2 行到第 N + 1 行（共 N 行），每行为一个正整数，表示第 i 块披萨的大小
     *
     * 1 ≤ i ≤ N
     * 披萨小块从某一块开始，按照一个方向次序顺序编号为 1 ~ N
     *
     * 每块披萨的大小范围为 [1, 2147483647]
     * 输出描述
     * "吃货"能分得到的最大的披萨大小的总和。
     *
     * @param args
     */
    @Override
    public void eatPizza(String[] args) {
        Scanner scanner= new Scanner(System.in);
        // 披萨的数量
        int n = scanner.nextInt();
        // 每块披萨的美味值
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }
        // 初始化记忆化数组，其维度为披萨数量的平方
        int dp[][]= new int[n][n];
        for(int[] row:dp){
            // 初始化记忆化数组，将所有值设为-1，表示未计算
            Arrays.fill(row,-1);
        }
        // 初始化最大美味值为0
        int  ans=0;
        // 遍历每块披萨，尝试以每块披萨作为起点计算最大美味值
        for(int i=0;i<n;i++){
            // 更新最大美味值，allocation函数计算从当前披萨开始的最大美味值
            ans=Math.max(ans,allocation(dp,a,(i+n)%n,(i+n-1)%n+a[i]));
        }
        System.out.println(ans);
    }

    /**
     * 计算值
     * @param left
     * @param right
     * @return
     */
    public int allocation( int[][]dp, int[] a, int left,int right) {
        // 如果当前状态已经计算过，则直接返回结果
        if (dp[left][right] != -1) {
            return dp[left][right];
        }
        // 根据贪心策略，选择当前美味值较大的披萨
        if (a[left] > a[right]) {
            // 如果左边的披萨更美味，则吃掉左边的披萨
            left = (left + 1) % a.length;
        } else {
            // 如果右边的披萨更美味，则吃掉右边的披萨
            right = (right + a.length - 1) % a.length;
        }
        // 如果只剩下一块披萨，则直接返回这块披萨的美味值
        if (left == right) {
            dp[left][right] = a[left];
        } else {
            // 否则，递归计算剩下披萨的最大美味值，并更新记忆化数组
            dp[left][right] = Math.max(a[left] + allocation(dp, a, (left + 1) % a.length, right), a[right] + allocation(dp, a, left, (right + a.length - 1) % a.length));
        }
        // 返回当前状态下的最大美味值
        return dp[left][right];
    }


    /**
     *NO. 6 光伏场地建设规划
     *
     * 题目描述
     * 祖国西北部有一片大片荒地，其中零星的分布着一些湖泊，保护区，矿区;
     * 整体上常年光照良好，但是也有一些地区光照不太好。
     *
     * 某电力公司希望在这里建设多个光伏电站，生产清洁能源对每平方公里的土地进行了发电评估，
     * 其中不能建设的区域发电量为0kw，可以发电的区域根据光照，地形等给出了每平方公里年发电量x千瓦。
     * 我们希望能够找到其中集中的矩形区域建设电站，能够获得良好的收益。
     *
     * 输入描述
     * 第一行输入为调研的地区长，宽，以及准备建设的电站【长宽相等，为正方形】的边长最低要求的发电量
     * 之后每行为调研区域每平方公里的发电量
     *
     * 输出描述
     * 输出为这样的区域有多少个
     *
     *
     * @param args
     */
    @Override
    public   void constructionPlan(String args[]){
        Scanner scanner = new Scanner(System.in);
        // 输入地区长length，宽width，电站边长size，最低发电量power
        int length = scanner.nextInt();
        int width = scanner.nextInt();
        int size = scanner.nextInt();
        int power = scanner.nextInt();
        // 输入每个区域每平方公里的发电量，存入矩阵matrix中
        int [][]powerGrid = new int[length][width];
        for(int i=0;i<=length;i++){
            for(int j=0;j<=width;j++){
                powerGrid[i][j]=scanner.nextInt();
            }
        }
        // 遍历所有可能的电站位置，计算该位置的矩形区域发电量
        int ans=0;
        for(int i=size;i<=length;i++){
            for(int j=size;j<=width;j++){
                int square=0;
                for(int x=i-size;x<i;x++){
                    for(int y=j-size;y<j;y++){
                        square+=powerGrid[x][y];
                    }
                }
                if(square>=power){
                    ans++;
                }

            }
            System.out.println("count="+ans);
        }

    }

    /**
     * NO. 7 恢复字符顺序
     * 题目描述
     * 对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1。
     *
     * 现给定一个按如上规则得到的打乱字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字。
     *
     * 输入描述
     * 输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。
     *
     * 输出描述
     * 输出一个数字，为序列中最小的数字。
     *
     *
     * @param args
     */
    @Override
    public void restoreCharacterSequece(String[] args) {
        // 创建一个Scanner对象，用于读取输入
        Scanner scanner = new Scanner(System.in);
        // 读取输入的打乱字符的字符串
        String s = scanner.next();
        // 读取输入的正整数序列的长度
        int k = scanner.nextInt();
        // 创建一个HashMap，用于统计打乱字符的字符串中各字符的数量
        HashMap<Character ,Integer> base = new HashMap<>();
        for(Character c :s.toCharArray()){
            base.put(c,base.getOrDefault(c,0)+1);
        }
        // 初始化滑动窗口的起始位置
        int i=1;
        // 当滑动窗口的起始位置小于等于1000减去序列长度加1时，继续循环
        while (i<=1000-k+1){
            // 创建一个HashMap，用于计算滑动窗口内各字符的数量
            HashMap<Character ,Integer> count = new HashMap<>();
            // 遍历滑动窗口内的正整数
            for(int j=i;j<i+k;j++){
                // 将正整数转换为字符串
                String nums = String.valueOf(j);
                // 遍历正整数字符串中的字符
                for(Character c :nums.toCharArray()){
                    // 将字符及其数量存入HashMap
                    base.put(c,base.getOrDefault(c,0)+1);
                }
            }
            // 初始化一个布尔变量，用于判断滑动窗口内各字符数量是否与打乱字符的字符串中各字符数量一致
            boolean isMatch=true;
            for(Character c :base.keySet()){
                // 如果滑动窗口内的字符数量与打乱字符的字符串中的字符数量不一致，将isMatch设为false并跳出循环
                if(!count.containsKey(c)||count.get(c)-base.get(c)!=0){
                    isMatch=false;
                    break;
                }
            }
            // 如果滑动窗口内各字符数量与打乱字符的字符串中各字符数量一致，则输出滑动窗口的起始位置并返回
            if(isMatch){
                System.out.println(i);
                return;
            }
            // 更新滑动窗口的起始位置
            i++;
        }



    }

    /**
     *  NO. 8矩形相交的面积
     *  题目描述
     * 给出3组点坐标(x, y, w, h)，-1000<x,y<1000，w,h为正整数。
     *
     * (x, y, w, h)表示平面直角坐标系中的一个矩形：
     *
     * x, y为矩形左上角坐标点，w, h向右w，向下h。
     *
     * (x, y, w, h)表示x轴(x, x+w)和y轴(y, y-h)围成的矩形区域；
     *
     * (0, 0, 2, 2)表示 x轴(0, 2)和y 轴(0, -2)围成的矩形区域；
     *
     * (3, 5, 4, 6)表示x轴(3, 7)和y轴(5, -1)围成的矩形区域；
     *
     * 求3组坐标构成的矩形区域重合部分的面积。
     *
     * 输入描述
     * 3行输入分别为3个矩形的位置，分别代表“左上角x坐标”，“左上角y坐标”，“矩形宽”，“矩形高” -1000 <= x,y < 1000
     *
     * 输出描述
     * 输出3个矩形相交的面积，不相交的输出0。
     *
     *
     * @param args
     */
    @Override
    public void intersectionArea(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 存储所有矩形的x坐标
        List<Integer> x_coods= new ArrayList<>();
        // 存储所有矩形的y坐标
        List<Integer> y_coods= new ArrayList<>();
        // 存储所有矩形的左上角和右下角坐标
        List<int[]> rects = new ArrayList<>();
        for(int i=0;i<3;i++){
            int x1=scanner.nextInt();
            int y1=scanner.nextInt();
            int w= scanner.nextInt();
            int h = scanner.nextInt();
            // 计算矩形的右上角x坐标
            int x2= x1+w;
            // 计算矩形的右上角y坐标
            int y2=y1-h;
            x_coods.add(x1);
            x_coods.add(x2);
            y_coods.add(y1);
            y_coods.add(y2);
            rects.add(new int[]{x1,y1,x2,y2});
        }
        int min_x = Integer.MAX_VALUE;
        int max_x = Integer.MIN_VALUE;
        int min_y = Integer.MAX_VALUE;
        int max_y = Integer.MIN_VALUE;
        for(int x :x_coods){
            min_x = Math.min(min_x,x);
            max_x = Math.max(max_x,x);
        }
        for(int y :y_coods){
            min_y = Math.min(min_y,y);
            max_y = Math.max(max_y,y);
        }
        // 计算x坐标的偏移量
        int x_offset = 0-min_x;
        // 计算y坐标的偏移量
        int y_offset = 0-min_y;
        int [][] area = new int[Math.abs(max_x-min_x)][Math.abs(max_y-min_y)];
        for(int [] rect:rects){
            int x1 = rect[0];
            int y1 = rect[1];
            int x2 = rect[2];
            int y2 = rect[3];
            for(int i=Math.min(x1,x2);i<Math.max(x1,x2)+x_offset;i++){
                for(int j=Math.min(y1,y2);i<Math.max(y1,y2)+y_offset;i++){
                    // 在相应的区域加1
                    area[i][j]+=1;
                }
            }

        }
     int ret=0;
        for(int i=0;i<area.length;i++){
            for(int j=0;j<area[0].length;j++){
                // 统计值为3的区域的个数
                if(area[i][j]==3){
                    ret+=1;
                }
            }
        }
// 输出相交的面积
        System.out.println(ret);
    }

    /**
     * 题目
     * 让我们来模拟一个消息队列的运作，有一个发布者和若干消费者，发布者会在给定的时刻向消息队列发送消息，若此时消息队列有消费者订阅，这个消息会被发送到订阅的消费者中优先级最高（输入中消费者按优先级升序排列）的一个； 若此时没有订阅的消费者，该消息被消息队列丢弃。 消费者则会在给定的时刻订阅消息队列或取消订阅。当消息发送和订阅发生在同一时刻时，先处理订阅操作，即同一时刻订阅的消费者成为消息发送的候选。 当消息发送和取消订阅发生在同一时刻时，先处理取消订阅操作，即消息不会被发送到同一时刻取消订阅的消费者。
     *
     * 输入描述
     * 输入为两行。
     *
     * 第一行为2N个正整数，代表发布者发送的N个消息的时刻和内容（为方便解折，消息内容也用正整数表示）。第一个数字是第一个消息的发送时刻，第二个数字是第一个消息的内容，以此类推。用例保证发送时刻不会重复，但注意消息并没有按照发送时刻排列。
     *
     * 第二行为2M个正整数，代表M个消费者订阅和取消订阅的时刻。第一个数字是第一个消费者订阅的时刻，第二个数字是第一个消费者取消订阅的时刻，以此类推。用例保证每个消费者的取消订阅时刻大于订阅时刻，消费者按优先级升序排列。
     *
     * 两行的数字都由空格分隔。N不超过100，M不超过10，每行的长度不超过1000字符
     *
     * 输出描述
     * 输出为M行，依次为M个消费者收到的消息内容，消息内容按收到的顺序排列，且由空格分隔；
     *
     * 若某个消费者没有收到任何消息，则对应的行输出-1
     * @param args
     */
    @Override
    public void simulateMq(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取并解析消息发布者的数据
        int[] msgArr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 读取并解析订阅者的数据
        int[] conArr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int msgLength= msgArr.length;
        // 将消息发布者的数据按时间和内容分组，存储为二维数组
        int [][] msgs = new int[msgLength/2][];
        for(int i=0,j=0;i<msgLength;i=i+2,j++){
            msgs[j]=new int[]{msgArr[i],msgArr[i+1]};
        }
        // 将订阅者的数据按订阅时间和退订时间分组，存储为二维数组
        int conLength = conArr.length;
        int [][] cons = new int[conLength/2][];
        for(int i=0,j=0;i<msgLength;i=i+2,j++){
            cons[j]=new int[]{conArr[i],conArr[i+1]};
        }
        // 按发布的时间对消息进行升序排序
        Arrays.sort(msgs,(x,y)->x[0]-y[0]);
        // 创建一个 ArrayList 用于存储每个订阅者接收到的消息
        ArrayList<ArrayList<Integer>> recieves = new ArrayList<>();
        for(int k=0;k<cons.length;k++){
            recieves.add(new ArrayList<>());
        }
        // 遍历所有发布的消息
        int pubIdx = 0;
        while (pubIdx < msgs.length) {
            int msgTime = msgs[pubIdx][0];  // 获取当前消息的发布时间
            int msgContent = msgs[pubIdx][1];  // 获取当前消息的内容
            // 遍历所有订阅者（从后往前遍历，优先分配给有效的订阅者）
            int subIdx = cons.length - 1;
            while (subIdx >= 0) {
                int subTime = cons[subIdx][0];  // 订阅者的订阅时间
                int unsubTime = cons[subIdx][1];  // 订阅者的退订时间
                // 如果消息发布时，订阅者处于有效订阅期
                if (msgTime >= subTime && msgTime < unsubTime) {
                    recieves.get(subIdx).add(msgContent);  // 该订阅者接收到消息
                    break;  // 找到一个有效的订阅者后就停止继续查找
                }
                subIdx--;  // 检查下一个订阅者
            }
            pubIdx++;  // 处理下一个发布的消息
        }

        // 输出每个订阅者接收到的消息内容
        int idx = 0;
        while (idx < recieves.size()) {
            ArrayList<Integer> contentList = recieves.get(idx);
            if (contentList.isEmpty()) {
                System.out.println("-1");  // 如果没有接收到任何消息，输出 -1
            } else {
                // 使用 StringJoiner 格式化输出接收到的消息内容
                StringJoiner sj = new StringJoiner(" ");
                for (int content : contentList) {
                    sj.add(Integer.toString(content));  // 添加每条消息
                }
                System.out.println(sj.toString());  // 输出消息内容
            }
            idx++;  // 处理下一个订阅者
        }

    }




    /**
     * No.10英文输入法
     *
     * 题目描述
     * 主管期望你来实现英文输入法单词联想功能。
     * 需求如下：
     *
     * 依据用户输入的单词前缀，从已输入的英文语句中联想出用户想输入的单词，按字典序输出联想到的单词序列，
     * 如果联想不到，请输出用户输入的单词前缀。
     * 注意：
     *
     * 英文单词联想时，区分大小写
     * 缩略形式如”don’t”，判定为两个单词，”don”和”t”
     * 输出的单词序列，不能有重复单词，且只能是英文单词，不能有标点符号
     * 输入描述
     * 输入为两行。
     *
     * 首行输入一段由英文单词word和标点符号组成的语句str；
     *
     * 接下来一行为一个英文单词前缀pre。
     *
     * 0 < word.length() <= 20
     * 0 < str.length <= 10000
     * 0 < pre <= 20
     * 输出描述
     * 输出符合要求的单词序列或单词前缀，存在多个时，单词之间以单个空格分割
     * @param args
     */
    @Override
    public   void enInput(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String sentence = br.readLine(); // 输入一段由英文单词word和标点符号组成的语句
        String prefix = br.readLine(); // 输入一个英文单词前缀
        sentence = sentence.replaceAll("[^a-zA-Z]", " "); // 将标点符号替换为空格
        Set<String> wordSet = new TreeSet<>(); // 存储单词的集合，自动去重且按照字典序排序
        String[] words = sentence.split("\\s+");
        for (String word : words) {
            wordSet.add(word);
        }
        StringBuilder ans = new StringBuilder();
        for (String s : wordSet) { // 遍历单词集合
            if (s.startsWith(prefix)) { // 如果单词以前缀开头
                ans.append(s).append(" "); // 将单词加入答案字符串
            }
        }
        if (ans.length() > 0) { // 如果答案字符串不为空
            System.out.println(ans.toString().trim()); // 输出单词序列
        } else {
            System.out.println(prefix); // 否则输出前缀
        }


    }

    /**
     * NO. 11 mvp 争夺战
     *
     *题目描述
     * 在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到MVP，MVP的条件是单场最高分得分获得者。
     * 可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，
     * 然而比赛过程中的每1分钟的得分都只能由某一个人包揽。
     *
     *
     *
     * 输入描述
     * 输入第一行为一个数字 t ，表示为有得分的分钟数 1 ≤ t ≤ 50
     * 第二行为 t 个数字，代表每一分钟的得分 p， 1 ≤ p ≤ 50
     *
     *
     *
     * 输出描述
     * 输出有得分的队员都是MVP时，最少得MVP得分。
     *
     * @param args
     * @throws IOException
     */

    @Override
    public void mvpWar(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();

        LinkedList<Integer> link = new LinkedList<>();
        /**
         * 获取得分
         */
        for (int i = 0; i < m; i++) {
            link.add(sc.nextInt());
        }

        System.out.println(getResult(link, m));
    }

    /**
     * 获取结果
     * @param link
     * @param m
     * @return
     */
    public static int getResult(LinkedList<Integer> link, int m) {
        /**
         * 正向排序
         */
        link.sort((a, b) -> b - a);

        /**
         * 累加比分
         */
        int sum = 0;
        for (Integer ele : link) {
            sum += ele;
        }

        while (m >= 1) {
            // 根据网友指正，由于canPartition方法中会删除link元素，因此我们不能直接传递link过去，需要传递link备份，否则会影响下一次count判断
            //      if (canPartitionMSubsets(link, sum, m)) return sum / m;
            LinkedList<Integer> link_cp = new LinkedList<>(link);
            if (canPartitionMSubsets(link_cp, sum, m)) return sum / m;
            m--;
        }

        return sum;
    }

    /**
     * 累加比分
     * @param link
     * @param sum
     * @param m
     * @return
     */
    public static boolean canPartitionMSubsets(LinkedList<Integer> link, int sum, int m) {
        /**
         * 总分除不尽 ，无效
         */
        if (sum % m != 0) return false;
        /**
         * 获取平均分
         */
        int subSum = sum / m;

        /**
         * 平均分小于最小得分也无效
         */
        if (subSum < link.get(0)) return false;

        //    while (link.get(0) == subSum) { // 此段代码可能会出现越界
        /**
         * 去除所有平均分的得分
         */
        while (link.size() > 0 && link.get(0) == subSum) {
            link.removeFirst();
            m--;
        }

        int[] buckets = new int[m];
        return partition(link, 0, buckets, subSum);
    }

    /**
     *
     * @param link
     * @param index
     * @param buckets
     * @param subSum
     * @return
     */
    public static boolean partition(LinkedList<Integer> link, int index, int[] buckets, int subSum) {
        /**
         * 已经遍历完
         */
        if (index == link.size()) return true;
        /**
         * 获取当前得分
         */
        int select = link.get(index);
        /**
         * 遍历结果集合
         */
        for (int i = 0; i < buckets.length; i++) {
            /**
             * 得分一致，跳出循环
             */
            if (i > 0 && buckets[i] == buckets[i - 1]) continue;
            /**
             * 满足条件时，继续玄幻
             */
            if (select + buckets[i] <= subSum) {
                buckets[i] += select;
                if (partition(link, index + 1, buckets, subSum)) return true;
                buckets[i] -= select;
            }
        }

        return false;
    }


    /**
     * NO. 12 查找单入口空闲区域
     *
     * 题目描述
     * 给定一个 m x n 的矩阵，由若干字符 ‘X’ 和 ‘O’构成，’X’表示该处已被占据，’O’表示该处空闲，请找到最大的单入口空闲区域。
     *
     * 解释：
     *
     * 空闲区域是由连通的’O’组成的区域，位于边界的’O’可以构成入口，
     *
     * 单入口空闲区域即有且只有一个位于边界的’O’作为入口的由连通的’O’组成的区域。
     * 如果两个元素在水平或垂直方向相邻，则称它们是“连通”的。
     *
     * 输入描述
     * 第一行输入为两个数字，第一个数字为行数m，第二个数字为列数n，两个数字以空格分隔，1<=m,n<=200。
     *
     * 剩余各行为矩阵各行元素，元素为‘X’或‘O’，各元素间以空格分隔。
     *
     * 输出描述
     * 若有唯一符合要求的最大单入口空闲区域，输出三个数字
     *
     * 第一个数字为入口行坐标（0~m-1）
     * 第二个数字为入口列坐标（0~n-1）
     * 第三个数字为区域大小
     * 三个数字以空格分隔；
     *
     * 若有多个符合要求，则输出区域大小最大的，若多个符合要求的单入口区域的区域大小相同，则此时只需要输出区域大小，不需要输出入口坐标。
     *
     * 若没有，输出NULL。
     * @param args
     * @throws IOException
     */

    /**
     * 已经遍历过的校验数组
     */
    static HashSet<String> checked = new HashSet<>();
    @Override
    public void singleEntry(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        /**
         * 数组长度
         */
         int n=sc.nextInt();;
        /**
         * 数据宽度
         */
       int m= sc.nextInt();
        /**
         * 具体数组
         */
       String[][] matrix = new String[n][m];
        /**
         * 接收数据
         */
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.next();
            }
        }

        System.out.println(getResult(matrix, n, m));
    }

    /**
     * 获取结果
     * @param matrix
     * @param n
     * @param m
     * @return
     */
    public static String getResult(String[][] matrix, int n, int m) {
        ArrayList<Integer[]> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //遍历未检查过的空闲区域
                if ("O".equals(matrix[i][j]) && !checked.contains(i + "-" + j)) {
                    ArrayList<Integer[]> enter = new ArrayList<>();
                    int count = dfs(matrix,n,m,i, j, 0, enter);
                    if (enter.size() == 1) {
                        Integer[] pos = enter.get(0);
                        Integer[] an = {pos[0], pos[1], count};
                        ans.add(an);
                    }
                }
            }
        }

        if (ans.size() == 0) return "NULL";
        ans.sort((a, b) -> b[2] - a[2]);

        if (ans.size() == 1 || ans.get(0)[2] > ans.get(1)[2]) {
            StringJoiner sj = new StringJoiner(" ", "", "");
            for (Integer ele : ans.get(0)) {
                sj.add(ele + "");
            }
            return sj.toString();
        } else {
            return ans.get(0)[2] + "";
        }

    }

    /**
     * 获取空闲区域数量
     * @param matrix
     * @param n
     * @param m
     * @param i
     * @param j
     * @param count
     * @param enter
     * @return
     */
    public static int dfs(String[][] matrix, int n, int m,int i, int j, int count, ArrayList<Integer[]> enter) {
        /**
         * 位置
         */
        String pos = i + "-" + j;
        /**
         * 非空闲区域直接返回
         */
        if (i < 0 || i >= n || j < 0 || j >= m || "X".equals(matrix[i][j]) || checked.contains(pos)) {
            return count;
        }
        /**
         * 记录已检查位置
         */
        checked.add(pos);

        /**
         * 如果搜索到的“O”的坐标位置处于矩阵第一列，或最后一列，或者第一行，或者最后一行，那么该“O”位置就是空闲区域的入口位置，我们将其缓存到out数组中
         */
        if (i == 0 || i == n - 1 || j == 0 || j == m - 1){
            enter.add(new Integer[]{i, j});
        }
        /**
         * 记录数量
         */
        count++;
        /**
         * 四个方向
         */
        int[][] offset = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        /**
         * 四个方向循环寻找位置
         */
        for (int k = 0; k < offset.length; k++) {
            int offsetX = offset[k][0];
            int offsetY = offset[k][1];

            int newI = i + offsetX;
            int newJ = j + offsetY;
            count = dfs(matrix,n,m,newI, newJ, count, enter);
        }

        return count;
    }

    /**
     * NO. 13货币单位换算
     * 题目描述
     * 记账本上记录了若干条多国货币金额，需要转换成人民币分（fen），汇总后输出。
     * 每行记录一条金额，金额带有货币单位，格式为数字+单位，可能是单独元，或者单独分，或者元与分的组合。
     * 要求将这些货币全部换算成人民币分（fen）后进行汇总，汇总结果仅保留整数，小数部分舍弃。
     * 元和分的换算关系都是1:100，如下：
     *
     * 1CNY=100fen（1元=100分）
     * 1HKD=100cents（1港元=100港分）
     * 1JPY=100sen（1日元=100仙）
     * 1EUR=100eurocents（1欧元=100欧分）
     * 1GBP=100pence（1英镑=100便士）
     * 汇率表如下：
     *
     * 即：100CNY = 1825JPY = 123HKD = 14EUR = 12GBP
     *
     * CNY	JPY	HKD	EUR	GBP
     * 100	1825	123	14	12
     * 输入描述
     * 第一行输入为N，N表示记录数。0<N<100
     *
     * 之后N行，每行表示一条货币记录，且该行只会是一种货币。
     *
     * 输出描述
     * 将每行货币转换成人民币分（fen）后汇总求和，只保留整数部分。
     * 输出格式只有整数数字，不带小数，不带单位。
     *
     *
     * @param args
     * @throws IOException
     */
    @Override
    public void curConvert(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in); // 创建Scanner对象用于读取输入
        int n = Integer.parseInt(scanner.nextLine()); // 读取记录数
        double totalFen = 0; // 汇总结果
        // 处理每一条货币记录
        for (int i = 0; i < n; i++) {
            String record = scanner.nextLine(); // 读取每一行的记录
            int amount = 0; // 用于保存金额
            StringBuilder unit = new StringBuilder(); // 保存单位

            // 遍历当前行，逐个提取金额和单位
            for (int j = 0; j < record.length(); j++) {
                char c = record.charAt(j);
                if (Character.isDigit(c)) {
                    amount = amount * 10 + (c - '0'); // 构建数字
                } else {
                    unit.append(c); // 构建货币单位
                }

                // 当遇到完整的金额+单位时进行换算
                if (j == record.length() - 1 || Character.isDigit(record.charAt(j + 1)) && unit.length() > 0) {
                    totalFen += amount * exChange(unit.toString()); // 计算并累加到总数
                    amount = 0; // 重置金额
                    unit.setLength(0); // 清空单位
                }
            }
        }

        // 输出汇总结果，只保留整数部分
        System.out.println((int) totalFen);
        scanner.close(); // 关闭Scanner对象



    }


    // 方法：根据货币单位返回其转换为人民币分的汇率
    public static double exChange(String unit) {
        switch (unit) {
            case "CNY":
                return 100.0; // 人民币
            case "JPY":
                return 100.0 / 1825 * 100; // 日元
            case "HKD":
                return 100.0 / 123 * 100; // 港元
            case "EUR":
                return 100.0 / 14 * 100; // 欧元
            case "GBP":
                return 100.0 / 12 * 100; // 英镑
            case "fen":
                return 1.0; // 人民币分
            case "cents":
                return 100.0 / 123; // 港元分
            case "sen":
                return 100.0 / 1825; // 日元分
            case "eurocents":
                return 100.0 / 14; // 欧元分
            case "pence":
                return 100.0 / 12; // 英镑分
            default:
                return 0.0; // 无效单位返回0
        }
    }

    /**
     * NO. 14 矩阵扩散
     * 题目描述
     * 存在一个m×n的二维数组，其成员取值范围为0或1。
     *
     * 其中值为1的成员具备扩散性，每经过1S，将上下左右值为0的成员同化为1。
     *
     * 二维数组的成员初始值都为0，将第[i,j]和[k,l]两个个位置上元素修改成1后，求矩阵的所有元素变为1需要多长时间。
     *
     * 输入描述
     * 输入数据中的前2个数字表示这是一个m×n的矩阵，m和n不会超过1024大小；
     *
     * 中间两个数字表示一个初始扩散点位置为i,j；
     *
     * 最后2个数字表示另一个扩散点位置为k,l。
     *
     * 输出描述
     * 输出矩阵的所有元素变为1所需要秒数。
     *
     * @param args
     * @throws IOException
     */
    @Override
    public void matrixExpand(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        Integer[] arr =
                Arrays.stream(sc.next().split(",")).map(Integer::parseInt).toArray(Integer[]::new);

        System.out.println(getResult(arr[0], arr[1], arr[2], arr[3], arr[4], arr[5]));
    }



    /**
     * @param m m m×n的二维数组
     * @param n n m×n的二维数组
     * @param i 扩散点位置为i,j
     * @param j 扩散点位置为i,j
     * @param k 扩散点位置为k,l
     * @param l 扩散点位置为k,l
     * @return 扩散所有点需要的时间
     */
    public static int getResult(int m, int n, int i, int j, int k, int l) {
        int[][] matrix = new int[m][n];
        matrix[i][j] = 1;
        matrix[k][l] = 1;

        // count记录未被扩散的点的数量
        int count = m * n - 2;

        // 多源BFS实现队列
        LinkedList<int[]> queue = new LinkedList<>();
        queue.addLast(new int[] {i, j});
        queue.addLast(new int[] {k, l});

        // 上下左右偏移量
        int[][] offsets = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        int day = 0;
        // 如果扩散点没有了，或者所有点已被扩散，则停止循环
        while (queue.size() > 0 && count > 0) {
            LinkedList<int[]> newQueue = new LinkedList<>();

            for (int[] pos : queue) {
                int x = pos[0];
                int y = pos[1];

                for (int[] offset : offsets) {
                    int newX = x + offset[0];
                    int newY = y + offset[1];

                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {
                        // 将点被扩散的时间记录为该点的值
                        matrix[newX][newY] = 1;
                        // 被扩散到的点将变为新的扩散源
                        newQueue.addLast(new int[] {newX, newY});
                        // 未被扩散点的数量--
                        count--;
                    }
                }
            }

            queue = newQueue;
            day++;
        }

        return day;
    }

    /**NO. 15 流水线
     * 题目描述
     * 一个工厂有m条流水线，来并行完成n个独立的作业，该工厂设置了一个调度系统，在安排作业时，总是优先执行处理时间最短的作业。
     *
     * 现给定流水线个数m，需要完成的作业数n, 每个作业的处理时间分别为t1,t2…tn。请你编程计算处理完所有作业的耗时为多少？
     *
     * 当n>m时，首先处理时间短的m个作业进入流水线，其他的等待，当某个作业完成时，依次从剩余作业中取处理时间最短的进入处理。
     *
     * 输入描述
     * 第一行为2个整数（采用空格分隔），分别表示流水线个数m和作业数n；
     *
     * 第二行输入n个整数（采用空格分隔），表示每个作业的处理时长t1,t2…tn。
     *
     * 0< m,n<100，0<t1,t2…tn<100。
     *
     * 注：保证输入都是合法的。
     *
     * 输出描述
     * 输出处理完所有作业的总时长。
     * @param args
     * @throws IOException
     */
    @Override
    public void pipeline(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        int[] times = new int[n];
        for (int i = 0; i < n; i++) times[i] = sc.nextInt();

        Arrays.sort(times);

        int[] mArr = new int[m];
        for (int i = 0; i < n; i++) {
            mArr[i % m] += times[i];
        }
        System.out.println(Arrays.stream(mArr).max().orElse(0));
    }


    /**
     * NO. 16 拼接URL
     * 题目描述
     * 给定一个url前缀和url后缀,通过,分割 需要将其连接为一个完整的url
     *
     * 如果前缀结尾和后缀开头都没有/，需要自动补上/连接符
     * 如果前缀结尾和后缀开头都为/，需要自动去重
     * 约束：不用考虑前后缀URL不合法情况
     *
     * 输入描述
     * url前缀(一个长度小于100的字符串)，url后缀(一个长度小于100的字符串)
     *
     *
     * 输出描述
     * 拼接后的url
     * @param args
     * @throws IOException
     */
    @Override
    public void concatUrl(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();

        String[] arr = s.split(",");

        String prefix = arr.length > 0 && arr[0].length() > 0 ? arr[0] : "/";
        String suffix = arr.length > 1 && arr[1].length() > 0 ? arr[1] : "/";
        prefix = prefix.replaceAll("/+$", "");
        suffix = suffix.replaceAll("^/+", "");
        String res= prefix + "/" + suffix;
        System.out.println(res);
    }

    /**
     *NO. 17 数组二叉树
     *
     * 题目描述
     * 二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2*N和2*N+1，并且我们用值-1代表一个节点为空。
     *
     * 给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。
     *
     * 输入描述
     * 输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。
     *
     * 注意第一个元素即为根节点的值，即数组的第N个元素对应下标N，下标0在树的表示中没有使用，所以我们省略了。
     *
     * 输入的树最多为7层。
     *
     * 输出描述
     * 输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个。
     * @param args
     * @throws IOException
     */
    @Override
    public void arrayBinaryTree(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        Integer[] arr =
                Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

        int n = arr.length - 1;

        // 最小叶子节点的值
        int min = Integer.MAX_VALUE;
        // 最小叶子节点的索引
        int minIdx = -1;
        // 求解最小叶子节点的值和索引
        for (int i = n; i >= 1; i--) {
            if (arr[i] != -1) {
                if (i * 2 + 1 <= n && arr[i * 2 + 1] != -1) //左节点非子节点
                    continue;
                if (i * 2 + 2 <= n && arr[i * 2 + 2] != -1) //有节点非子节点
                    continue;
                if (min > arr[i]) {
                    min = arr[i];
                    minIdx = i;
                }
            }
        }

        // path用于缓存最小叶子节点到根的路径
        LinkedList<Integer> path = new LinkedList<>();
        path.addFirst(min);

        // 从最小叶子节点开始向上找父节点，直到树顶
        while (minIdx != 0) {
            int f = (minIdx - 1) / 2;
            path.addFirst(arr[f]);
            minIdx = f;
        }

        StringJoiner sj = new StringJoiner(" ");
        for (Integer val : path) sj.add(val + "");
        System.out.println(sj);

    }

    /**
     *  NO. 18 数组组成的最小数字
     *  题目描述
     * 给定一个整型数组，请从该数组中选择3个元素组成最小数字并输出
     *
     * （如果数组长度小于3，则选择数组中所有元素来组成最小数字）。
     *
     * 输入描述
     * 一行用半角逗号分割的字符串记录的整型数组，0 < 数组长度 <= 100，0 < 整数的取值范围 <= 10000。
     *
     * 输出描述
     * 由3个元素组成的最小数字，如果数组长度小于3，则选择数组中所有元素来组成最小数字。
     * @param args
     * @throws IOException
     */
    @Override
    public void minDigital(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        String[] strs = sc.nextLine().split(",");
        Arrays.sort(strs, (a, b) -> Integer.parseInt(a) - Integer.parseInt(b));
        String[] tmp = Arrays.copyOfRange(strs, 0, Math.min(3, strs.length));
        Arrays.sort(tmp, (a, b) -> (a + b).compareTo(b + a));
        StringBuilder sb = new StringBuilder();
        for (String s : tmp) {
            sb.append(s);
        }

        System.out.println(sb);
    }

    /**
     *  NO. 19 游戏分组
     * 题目描述
     * 部门准备举办一场王者荣耀表演赛，有 10 名游戏爱好者参与，分为两队，每队 5 人。
     *
     * 每位参与者都有一个评分，代表着他的游戏水平。为了表演赛尽可能精彩，我们需要把 10 名参赛者分为示例尽量相近的两队。
     *
     * 一队的实力可以表示为这一队 5 名队员的评分总和。
     *
     * 现在给你 10 名参与者的游戏水平评分，请你根据上述要求分队，最后输出这两组的实力差绝对值。
     *
     * 例：10 名参赛者的评分分别为：5 1 8 3 4 6 7 10 9 2，分组为（1 3 5 8 10）和（2 4 6 7 9），两组实力差最小，差值为1。有多种分法，但是实力差的绝对值最小为1。
     *
     * 输入描述
     * 10个整数，表示10名参与者的游戏水平评分。范围在 [1, 10000] 之间。
     *
     * 输出描述
     * 1个整数，表示分组后两组实力差绝对值的最小值。
     * @param args
     * @throws IOException
     */

    @Override
    public void gameGroup(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int[] arr = new int[10];
        for (int i = 0; i < 10; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);

        ArrayList<Integer> res = new ArrayList<>();
        // dfs求10选5的去重组合，并将组合之和记录进res中，即res中记录的是所有可能性的5人小队实力值之和
        dfs(arr, 0, 0, 0, res);

        int sum = Arrays.stream(arr).reduce(Integer::sum).orElse(0);
        // 某队实力为subSum，则另一队实力为sum - subSum，则两队实力差为 abs((sum - subSum) - subSum)，先求最小实力差
        int min = res.stream().map(subSum -> Math.abs(sum - 2 * subSum)).min((a, b) -> a - b).orElse(0);
        System.out.println(min);
    }

    // 求解去重组合
    public static void dfs(int[] arr, int index, int level, int sum, ArrayList<Integer> res) {
        if (level == 5) {
            res.add(sum);
            return;
        }

        for (int i = index; i < 10; i++) {
            if (i > index && arr[i] == arr[i - 1]) continue; // arr已经升序，这里进行树层去重
            dfs(arr, i + 1, level + 1, sum + arr[i], res);
        }
    }


    /**
     * NO. 20  整理扑克牌
     * 题目描述
     * 给定一组数字，表示扑克牌的牌面数字，忽略扑克牌的花色，请按如下规则对这一组扑克牌进行整理：
     *
     * 步骤1. 对扑克牌进行分组，形成组合牌，规则如下：
     *
     * 当牌面数字相同张数大于等于4时，组合牌为“炸弹”；
     * 3张相同牌面数字 + 2张相同牌面数字，且3张牌与2张牌不相同时，组合牌为“葫芦”；
     * 3张相同牌面数字，组合牌为“三张”；
     * 2张相同牌面数字，组合牌为“对子”；
     * 剩余没有相同的牌，则为“单张”；
     * 步骤2. 对上述组合牌进行由大到小排列，规则如下：
     *
     * 不同类型组合牌之间由大到小排列规则：“炸弹” > “葫芦” > “三张” > “对子” > “单张”；
     * 相同类型组合牌之间，除“葫芦”外，按组合牌全部牌面数字加总由大到小排列；
     * “葫芦”则先按3张相同牌面数字加总由大到小排列，3张相同牌面数字加总相同时，再按另外2张牌面数字加总由大到小排列；
     * 由于“葫芦”>“三张”，因此如果能形成更大的组合牌，也可以将“三张”拆分为2张和1张，其中的2张可以和其它“三张”重新组合成“葫芦”，剩下的1张为“单张”
     * 步骤3. 当存在多个可能组合方案时，按如下规则排序取最大的一个组合方案：
     *
     * 依次对组合方案中的组合牌进行大小比较，规则同上；
     * 当组合方案A中的第n个组合牌大于组合方案B中的第n个组合牌时，组合方案A大于组合方案B；
     * 输入描述
     * 第一行为空格分隔的N个正整数，每个整数取值范围[1,13]，N的取值范围[1,1000]
     *
     * 输出描述
     * 经重新排列后的扑克牌数字列表，每个数字以空格分隔
     * @param args
     */
    @Override
    public void sortPokerGame(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine();
        Integer[] arr = Arrays.stream(str.split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

        HashMap<Integer, Integer> card = new HashMap<>();

        // 统计各种牌面的数量
        for (Integer num : arr) {
            if (card.containsKey(num)) {
                int val = card.get(num);
                card.put(num, ++val);
            } else {
                card.put(num, 1);
            }
        }

        // 统计组合，4代表炸弹，3+2代表葫芦，3代表三张，2代表对子，1代表单张
        HashMap<String, LinkedList<Integer[]>> combine = new HashMap<>();
        combine.put("4", new LinkedList<Integer[]>());
        combine.put("3+2", new LinkedList<Integer[]>());
        combine.put("3", new LinkedList<Integer[]>());
        combine.put("2", new LinkedList<Integer[]>());
        combine.put("1", new LinkedList<Integer[]>());

        // 首先将初始组合统计出来
        Set<Integer> cardKeys = card.keySet();
        for (Integer num : cardKeys) {
            switch (card.get(num)) {
                case 3:
                    combine.get("3").add(new Integer[] {num});
                    break;
                case 2:
                    combine.get("2").add(new Integer[] {num});
                    break;
                case 1:
                    combine.get("1").add(new Integer[] {num});
                    break;
                default:
                    combine
                            .get("4")
                            .add(
                                    new Integer[] {
                                            num, card.get(num)
                                    }); // 由于炸弹可能有4张以上相同牌面组成，因此既需要统计牌面num，也需要统计牌数card[num]
            }
        }

        // 炸弹排序
        combine.get("4").sort((a, b) -> !Objects.equals(a[1], b[1]) ? b[1] - a[1] : b[0] - a[0]);

        // 三张排序，牌面值越大，三张越大
        combine.get("3").sort((a, b) -> b[0] - a[0]);

        // 对子排序，牌面值越大，对子越大
        combine.get("2").sort((a, b) -> b[0] - a[0]);

        // 尝试组合出葫芦
        while (combine.get("3").size() > 0) {
            // 如果对子用完，三张还有一个，那么可以直接结束循环
            if (combine.get("2").size() == 0 && combine.get("3").size() == 1) break;

            // 否则，选取一个最大的三张
            Integer san_top = combine.get("3").removeFirst()[0];

            Integer tmp;
            // 如果此时没有对子了，胡总和第二大的三张的牌面，比最大的对子牌面大，则可以拆分三张，组合出葫芦
            if (combine.get("2").size() == 0
                    || (combine.get("3").size() > 0
                    && combine.get("3").get(0)[0] > combine.get("2").get(0)[0])) {
                tmp = combine.get("3").removeFirst()[0];
                // 拆分三张为对子的话，会多出一个单张
                combine.get("1").add(new Integer[] {tmp});
            } else {
                // 如果对子牌面比三张大，则不需要拆分三张，直接使用对子组合出葫芦
                tmp = combine.get("2").removeFirst()[0];
            }
            combine.get("3+2").add(new Integer[] {san_top, tmp}); // 葫芦元素含义：[三张牌面，对子牌面]
        }

        // 处理完葫芦后，就可以对单张进行降序了（因为组合葫芦的过程中，可能产生新的单张，因此单张排序要在葫芦组合得到后进行）
        combine.get("1").sort((a, b) -> b[0] - a[0]);

        // ans存放题解
        ArrayList<Integer> ans = new ArrayList<>();

        // 首先将炸弹放到ans中
        for (Integer[] vals : combine.get("4")) {
            int score = vals[0];
            int count = vals[1];
            for (int i = 0; i < count; i++) {
                ans.add(score);
            }
        }

        // 然后将葫芦放大ans中
        for (Integer[] vals : combine.get("3+2")) {
            int san = vals[0];
            int er = vals[1];
            for (int i = 0; i < 3; i++) ans.add(san);
            for (int i = 0; i < 2; i++) ans.add(er);
        }

        // 之后将三张放到ans中
        for (Integer[] vals : combine.get("3")) {
            for (int i = 0; i < 3; i++) ans.add(vals[0]);
        }

        // 接着是对子放到ans中
        for (Integer[] vals : combine.get("2")) {
            for (int i = 0; i < 2; i++) ans.add(vals[0]);
        }

        // 最后是单张放到ans中
        for (Integer[] vals : combine.get("1")) {
            ans.add(vals[0]);
        }

        StringJoiner sj = new StringJoiner(" ");
        for (Integer an : ans) {
            sj.add(an + "");
        }
        System.out.println(sj);
    }

    /**
     * NO. 21  字符串分割
     * 给定一个非空字符串S，其被N个‘-’分隔成N+1的子串，给定正整数K，要求除第一个子串外，其余的子串每K个字符组成新的子串，并用‘-’分隔。对于新组成的每一个子串，如果它含有的小写字母比大写字母多，则将这个子串的所有大写字母转换为小写字母；反之，如果它含有的大写字母比小写字母多，则将这个子串的所有小写字母转换为大写字母；大小写字母的数量相等时，不做转换
     *
     * 输入描述
     * 输入为两行，第一行为参数K，第二行为字符串S
     *
     * 输出描述
     * 输出转换后的字符串
     * @param args
     */
    @Override
    public void splitStr(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int K = scanner.nextInt();  // 每个子字符串的最大长度
        String inputString = scanner.next();  // 输入的字符串
        // 按照 "-" 将输入字符串分割成多个部分
        String[] sections = inputString.split("-");
        // 使用队列来存储分割后的各个部分
        Queue<String> queue = new LinkedList<>(Arrays.asList(sections));

        // 创建 StringBuilder 来构建最终的结果字符串
        StringBuilder finalResult = new StringBuilder(queue.poll());  // 先将第一个部分添加到最终结果
        // 使用 StringBuilder 来存储剩余部分的字符
        StringBuilder buffer = new StringBuilder();
        // 将队列中的剩余部分合并到一个缓冲区中
        while (!queue.isEmpty()) {
            buffer.append(queue.poll());
        }
        // 记录当前子字符串中小写字母和大写字母的数量
        int lowerCount = 0, upperCount = 0;
        // 用于暂时存储当前正在处理的子字符串
        StringBuilder segmentBuilder = new StringBuilder();
        // 遍历缓冲区的每个字符
        for (int i = 0; i < buffer.length(); i++) {
            char current = buffer.charAt(i);  // 当前字符

            // 根据字符的大小写分别统计小写和大写字母的数量
            if (Character.isLowerCase(current)) lowerCount++;
            else if (Character.isUpperCase(current)) upperCount++;
            // 将当前字符添加到当前子字符串的构建器中
            segmentBuilder.append(current);
            // 如果当前子字符串已达到最大长度 K 或是最后一个字符
            if ((i + 1) % K == 0 || i == buffer.length() - 1) {
                // 根据小写字母和大写字母的数量决定如何处理当前子字符串
                if (lowerCount > upperCount) {
                    finalResult.append("-").append(segmentBuilder.toString().toLowerCase());
                } else if (upperCount > lowerCount) {
                    finalResult.append("-").append(segmentBuilder.toString().toUpperCase());
                } else {
                    finalResult.append("-").append(segmentBuilder.toString());
                }
                // 重置计数器和子字符串构建器
                lowerCount = 0;
                upperCount = 0;
                segmentBuilder.setLength(0);  // 清空当前的子字符串
            }
        }
        System.out.println(finalResult);

    }

    /**
     * NO. 22  字符串序列判定
     *
     * 题目描述
     * 输入两个字符串 S 和 L ，都只包含英文小写字母。S长度 ≤ 100，L长度 ≤ 500,000。判定S是否是L的有效子串。
     *
     * 判定规则：S 中的每个字符在 L 中都能找到（可以不连续），且 S 在Ｌ中字符的前后顺序与 S 中顺序要保持一致。（例如，S = ”ace” 是 L= ”abcde” 的一个子序列且有效字符是a、c、e，而”aec”不是有效子序列，且有效字符只有a、e）
     *
     * 输入描述
     * 输入两个字符串 S 和 L，都只包含英文小写字母。S长度 ≤ 100，L长度 ≤ 500,000。
     *
     * 先输入S，再输入L，每个字符串占一行。
     *
     * 输出描述
     * S 串最后一个有效字符在 L 中的位置。（首位从0开始计算，无有效字符返回-1）
     * @param args
     */
    @Override
    public void strSeqDetermin(String[] args) {
        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();
        String l = sc.nextLine();
        int i = 0;
        int j = 0;

        while (i < s.length() && j < l.length()) {
            if (s.charAt(i) == l.charAt(j)) {
                i++;
            }
            j++;
        }
        int result = -1;
        if (i == s.length()){
            result= j - 1;
        }
        System.out.println(result);
    }

    /**
     *  NO. 23  最大数字
     *给定一个由纯数字组成以字符串表示的数值，现要求字符串中的每个数字最多只能出现2次，超过的需要进行删除；
     *
     * 删除某个重复的数字后，其它数字相对位置保持不变。
     *
     * 如”34533″，数字3重复超过2次，需要删除其中一个3，删除第一个3后获得最大数值”4533″
     *
     * 请返回经过删除操作后的最大的数值，以字符串表示。
     *
     * 输入描述
     * 第一行为一个纯数字组成的字符串，长度范围：[1,100000]
     *
     * 输出描述
     * 输出经过删除操作后的最大的数值
     *
     * @param args
     */
    @Override
    public void biggestNum(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        // 每个数字字符的可用个数
        HashMap<Character, Integer> unused = new HashMap<>();
        // 每个数字字符的保留个数
        HashMap<Character, Integer> reserve = new HashMap<>();

        // 初始时，每个数字有多少个，就可用多少个，由于还未使用，因此保留个数为0
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            unused.put(c, unused.getOrDefault(c, 0) + 1);
            reserve.putIfAbsent(c, 0);
        }
        // 定义一个栈
        LinkedList<Character> stack = new LinkedList<>();
        // 遍历输入字符串的每个数字字符c
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            // 如果该字符已经保留了2个了，则后续再出现该数字字符可以不保留
            if (reserve.get(c) == 2) {
                // 则可用c数字个数--
                unused.put(c, unused.get(c) - 1);
                continue;
            }

            // 比较当前数字c和栈顶数字top，如果c>top，那么需要考虑将栈顶数字弹出
            while (stack.size() > 0) {
                char top = stack.getLast();

                // 如果栈顶数字被弹出后，已保留的top字符数量和未使用的top字符数量之和大于等于2，则可以弹出，否则不可以
                if (top < c && unused.get(top) + reserve.get(top) - 1 >= 2) {
                    stack.removeLast();
                    reserve.put(top, reserve.get(top) - 1);
                } else {
                    break;
                }
            }

            // 选择保留当前遍历的数字c
            stack.add(c);
            // 则可用c数字个数--
            unused.put(c, unused.get(c) - 1);
            // 已保留c数字个数++
            reserve.put(c, reserve.get(c) + 1);
        }
        StringBuilder sb = new StringBuilder();
        for (Character c : stack) {
            sb.append(c);
        }
      System.out.println(sb);



    }

    /**
     * 最长的指定瑕疵度的元音子串
     *
     * 开头和结尾都是元音字母（aeiouAEIOU）的字符串为元音字符串，其中混杂的非元音字母数量为其瑕疵度。比如:
     *
     * “a” 、 “aa”是元音字符串，其瑕疵度都为0
     * “aiur”不是元音字符串（结尾不是元音字符）
     *  “abira”是元音字符串，其瑕疵度为2
     * 给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，如果找不到满足条件的元音字符子串，输出0。
     *
     * 子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。
     *
     * 输入描述
     * 首行输入是一个整数，表示预期的瑕疵度flaw，取值范围[0, 65535]。
     *
     * 接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度(0, 65535]。
     *
     * 输出描述
     * 输出为一个整数，代表满足条件的元音字符子串的长度。
     * @param args
     */
    @Override
    public void longestStr(String[] args) {
        Scanner sc = new Scanner(System.in);
        /**
         *预期的瑕疵度
         */
        int flaw = sc.nextInt();
        /**
         *字符串
         */
        String s = sc.next();
        /**
         * 元音字母
         */
        char[] yuan = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        HashSet<Character> set = new HashSet<>();
        for (char c : yuan){
            set.add(c);
        }

        /**
         * 保存字符串中存在元音字母的位置
         */
        ArrayList<Integer> idxs = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
                idxs.add(i);
            }

        }
        int ans = 0;
        int n = idxs.size();

        /**
         * 左右指针
         */
        int l = 0;
        int r = 0;

        while (r < n) {
            // 瑕疵度计算
            int diff = idxs.get(r) - idxs.get(l) - (r - l);

            if (diff > flaw) {
                l++;
            } else if (diff < flaw) {
                r++;
            } else {
                ans = Math.max(ans, idxs.get(r) - idxs.get(l) + 1);
                r++;
            }
        }
        System.out.println(ans);

    }

    /**
     * NO. 25 斗地主之顺子
     * 题目描述
     * 在斗地主扑克牌游戏中， 扑克牌由小到大的顺序为：3,4,5,6,7,8,9,10,J,Q,K,A,2，玩家可以出的扑克牌阵型有：单张、对子、顺子、飞机、炸弹等。
     *
     * 其中顺子的出牌规则为：由至少5张由小到大连续递增的扑克牌组成，且不能包含2。
     *
     * 例如：{3,4,5,6,7}、{3,4,5,6,7,8,9,10,J,Q,K,A}都是有效的顺子；而{J,Q,K,A,2}、 {2,3,4,5,6}、{3,4,5,6}、{3,4,5,6,8}等都不是顺子。
     *
     * 给定一个包含13张牌的数组，如果有满足出牌规则的顺子，请输出顺子。
     *
     * 如果存在多个顺子，请每行输出一个顺子，且需要按顺子的第一张牌的大小（必须从小到大）依次输出。
     *
     * 如果没有满足出牌规则的顺子，请输出No。
     *
     * 输入描述
     * 13张任意顺序的扑克牌，每张扑克牌数字用空格隔开，每张扑克牌的数字都是合法的，并且不包括大小王：
     *
     * 2 9 J 2 3 4 K A 7 9 A 5 6
     *
     * 不需要考虑输入为异常字符的情况
     *
     * 输出描述
     * 组成的顺子，每张扑克牌数字用空格隔开：
     *
     * 3 4 5 6 7
     * @param args
     */
    @Override
    public void pokerGame(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] strs = new String[13];
        for(int i = 0; i < 13; i++){
            strs[i]=scanner.next();
        }
        scanner.close();
        List<Integer> cardList = new ArrayList<>();
        for(String card:strs){
            if(!"2".equals(card)){
                cardList.add(getInteger(card));
            }

        }
        Collections.sort(cardList);
        List<List<Integer>> sequences = new ArrayList<>();
        boolean[] used = new boolean[cardList.size()]; // 记录每张牌是否已被使用

        for(int i=0;i<cardList.size();i++){
            if(used[i]){
                continue;
            }
            List<Integer> currentSeq = new ArrayList<>();
            currentSeq.add(cardList.get(i));
            used[i]=true;
            for(int j=i+1;j<cardList.size();j++){
                if(used[j]){
                    continue;
                }
                if(cardList.get(j)==currentSeq.get(currentSeq.size()-1)+1){
                    currentSeq.add(cardList.get(j));
                    used[j]=true;
                }else{
                    break;
                }


            }
            if(currentSeq.size()>4){
                sequences.add(new ArrayList<>(currentSeq));
            }else{
                for(Integer num:currentSeq){
                    used[cardList.indexOf(num)]=false;
                }
            }
        }
        if(sequences.size()==0){
            System.out.println("NO");
        }else{
            for(List<Integer> seqList :sequences){
                StringBuffer sb = new StringBuffer();
                for(int num :seqList){
                    sb.append(getString(num));
                    sb.append(" ");
                }
                System.out.println(sb.toString());
            }
        }

    }

    /**
     *
     * @param card
     * @return
     */
    static int getInteger(String card){
        int num =0;
        switch (card){
            case "J" :
                num= 11;
                break;
            case "Q" :
                num= 12;
                break;
            case "K" :
                num= 13;
                break;
            case "A" :
                num= 14;
                break;
            case "2" :
                num= 0;
                break;
            default:
                num= Integer.valueOf(card);
                break;
        }
        return num;

    }


    /**
     *
     * @param card
     * @return
     */
    static   String getString(int card){
        String str ="";
        switch (card){
            case 11 :
                str= "J";
                break;
            case 12 :
                str= "Q" ;
                break;
            case 13 :
                str= "K";
                break;
            case 14 :
                str= "A";
                break;
            case 0 :
                str= "2";
                break;
            default:
                str= String.valueOf(card);
                break;
        }
        return str;

    }

    @Override
    public void luckyGame(String[] args) {
        Scanner input = new Scanner(System.in);

        // 输入矩阵的行数和列数
        int rowCount = input.nextInt();
        int colCount = input.nextInt();

        // 初始化矩阵
        int[][] matrix = new int[rowCount][colCount];
        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < colCount; j++) {
                matrix[i][j] = input.nextInt();
            }
        }
        // 标记矩阵，用于记录某个位置是否已访问
        boolean[][] marked = new boolean[rowCount][colCount];
        // 初始化连通块计数器
        int clickCount = 0;
        // 遍历矩阵的每个元素
        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < colCount; j++) {
                // 如果当前元素是未访问的'1'，视为新连通块
                if (matrix[i][j] == 1 && !marked[i][j]) {
                    clickCount++;
                    // 使用队列进行BFS
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j});
                    marked[i][j] = true; // 标记为已访问

                    // BFS遍历连通块中的所有元素
                    while (!queue.isEmpty()) {
                        int[] point = queue.poll(); // 取出队列头部的坐标
                        int x = point[0];
                        int y = point[1];

                        // 遍历当前位置的八个方向
                        for (int[] dir : new int[][]{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}) {
                            int newX = x + dir[0];
                            int newY = y + dir[1];

                            // 检查新坐标是否在矩阵范围内，且是未访问的'1'
                            if (newX >= 0 && newX < rowCount && newY >= 0 && newY < colCount && matrix[newX][newY] == 1 && !marked[newX][newY]) {
                                marked[newX][newY] = true; // 标记新坐标为已访问
                                queue.add(new int[]{newX, newY}); // 将新坐标加入队列
                            }
                        }
                    }
                }
            }
        }

      System.out.println(clickCount);
    }


    /**
     * NO. 27 流浪地球
     *
     * 流浪地球计划在赤道上均匀部署了N个转向发动机，按位置顺序编号为0~N-1。
     *
     * 初始状态下所有的发动机都是未启动状态;
     * 发动机启动的方式分为”手动启动"和”关联启动"两种方式;
     * 如果在时刻1一个发动机被启动，下一个时刻2与之相邻的两个发动机就会被”关联启动”;
     * 如果准备启动某个发动机时，它已经被启动了，则什么都不用做;
     * 发动机0与发动机N-1是相邻的;
     * 地球联合政府准备挑选某些发动机在某些时刻进行“手动启动”。当然最终所有的发动机都会被启动。
     *
     * 哪些发动机最晚被启动呢?
     *
     * 输入描述
     * 第一行两个数字N和E，中间有空格
     * N代表部署发动机的总个数，E代表计划手动启动的发动机总个数
     * 1<N<=1000,1<=E<=1000,E<=N
     * 接下来共E行，每行都是两个数字T和P，中间有空格
     * T代表发动机的手动启动时刻，P代表此发动机的位置编号。
     * 0<=T<=N.0<=P<N
     * 输出描述
     * 第一行一个数字N，以回车结束
     * N代表最后被启动的发动机个数
     * 第二行N个数字，中间有空格，以回车结束
     * 每个数字代表发动机的位置编号，从小到大排序
     * @param args
     */
    @Override
    public   void wanderingEearth(String args[]){
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int activeCount = scanner.nextInt();
        int [] activeTime = new int[total];
        boolean [] visited = new boolean[total];
        Arrays.fill(activeTime,-1);
        PriorityQueue<int []> pq = new PriorityQueue<>(Comparator.comparingInt(info->info[0]));
        for(int i=0;i<activeCount;i++){
            int time = scanner.nextInt();
            int position = scanner.nextInt();
            if(activeTime[position]==-1){
                activeTime[position]=time;
                pq.offer(new int[]{time,position});
            }
        }
        while (!pq.isEmpty()){
            int [] cur = pq.poll();
            int time = cur[0];
            int position = cur[1];
            if(visited[position]){
                continue;
            }

            visited[position]=true;
            int nextTime = time+1;
            int []nbs = {(position-1+total)%total,(position+1)%total};
            for(int nb :nbs){
                if(activeTime[nb]==-1||activeTime[nb]>nextTime){
                    activeTime[nb]=nextTime;
                    if(!visited[nb]){
                        pq.offer(new int[]{nextTime,nb});
                    }
                }
            }
        }
        int maxTime =Arrays.stream(activeTime).max().orElse(-1);
        List<Integer> lastTimeList = new ArrayList<>();
        for(int i=0;i<total;i++){
            if(activeTime[i]==maxTime){
                lastTimeList.add(i);
            }
        }
        System.out.println(lastTimeList.size());
        lastTimeList.stream().forEach(System.out::println);
    }

    /**
     *  NO. 28 任务总执行时长
     *  题目
     * 任务编排服务负责对任务进行组合调度。参与编排的任务有两种类型，其中一种执行时长为taskA，另一种执行时长为taskB。任务一旦开始执行不能被打断，且任务可连续执行。服务每次可以编排num个任务。请编写一个方法，生成每次编排后的任务所有可能的总执行时长。
     *
     * 输入描述
     * 第1行输入分别为
     *
     * 第1种任务执行时长taskA 第2种任务执行时长taskB 这次要编排的任务个数num 以逗号分隔
     *
     * 输出描述
     * 数组形式返回所有总执行时时长，需要按从小到大排列。
     *
     * 备注 注：每种任务的数量都大于本次可以编排的任务数量
     *
     * 0 < taskA 0 < taskB 0 <= num <= 100000
     *
     * @param args
     */
    @Override
    public void completeTaskTime(String[] args) {
        Scanner input = new Scanner(System.in);

        // 读取输入并分割为 tA, tB 和 count
        String[] data = input.nextLine().split(",");
        int tA = Integer.parseInt(data[0]); // tA的值
        int tB = Integer.parseInt(data[1]); // tB的值
        int count = Integer.parseInt(data[2]); // count的值
        if (count == 0)
            System.out.println("[]");
        // 使用 TreeSet 来自动去重并按升序排列
        Set<Integer> times = new TreeSet<>();
        // 计算 i 从 0 到 count 的所有可能的 tA * i + tB * (count - i)
        for (int i = 0; i <= count; i++) {
            times.add(tA * i + tB * (count - i));
        }
        System.out.println(times.toString());


    }
    /**
     *  NO. 29 事件推送
     *  同一个数轴X上有两个点的集合A={A1, A2, …, Am}和B={B1, B2, …, Bn}，Ai和Bj均为正整数，A、B已经按照从小到大排好序，A、B均不为空，给定一个距离R(正整数)，列出同时满足如下条件的所有（Ai, Bj）数对：Ai <= Bj Ai, Bj之间的距离小于等于R 在满足1,2的情况下,每个Ai只需输出距离最近的Bj 输出结果按Ai从小到大的顺序排序
     *
     * 输入描述
     * 第一行三个正整数m,n,R
     *
     * 第二行m个正整数,表示集合A
     *
     * 第三行n个正整数,表示集合B
     *
     * 输入限制：
     *
     * 1<=R<=100000, 1<=n,m<=100000, 1<=Ai,Bj<=1000000000
     *
     * 输出描述
     * 每组数对输出一行Ai和Bj,以空格隔开
     *
     *
     *
     *
     * @param args
     */
    @Override
    public void eventPush(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取 m、n、r
        int m = sc.nextInt();
        int n = sc.nextInt();
        int r = sc.nextInt();

        int[] setA = new int[m];
        int[] setB = new int[n];
        // 读取数组 A
        for (int x = 0; x < m; x++) {
            setA[x] = sc.nextInt();
        }
        // 读取数组 B
        for (int y = 0; y < n; y++) {
            setB[y] = sc.nextInt();
        }
        Arrays.sort(setB); // 先对 B 进行排序，确保双指针法可行
        int indexB = 0; // 指向 B 中当前检查的元素
        // 遍历数组 A 中的每个元素
        for (int valueA : setA) {
            // 移动 indexB，使其指向 >= valueA 的最小元素
            while (indexB < setB.length && setB[indexB] < valueA) {
                indexB++;
            }
            // 检查是否满足误差范围
            if (indexB < setB.length && setB[indexB] - valueA <= r) {
                System.out.println(valueA + " " + setB[indexB]);
            }
        }


    }
    /**
     *  NO. 30 增强的strstr
     *C 语言有一个库函数： char *strstr(const char *haystack, const char *needle) ，实现在字符串 haystack 中查找第一次出现字符串 needle 的位置，如果未找到则返回 null。
     *
     * 现要求实现一个strstr的增强函数，可以使用带可选段的字符串来模糊查询，与strstr一样返回首次查找到的字符串位置。
     *
     * 可选段使用“[]”标识，表示该位置是可选段中任意一个字符即可满足匹配条件。比如“a[bc]”表示可以匹配“ab”或“ac”。
     *
     * 注意目标字符串中可选段可能出现多次。
     *
     * 输入描述
     * 与strstr函数一样，输入参数是两个字符串指针，分别是源字符串和目标字符串。
     *
     * 输出描述
     * 与strstr函数不同，返回的是源字符串中，匹配子字符串相对于源字符串地址的偏移（从0开始算），如果没有匹配返回-1。
     *
     * 补充说明：源字符串中必定不包含‘[]’；目标字符串中‘[]’必定成对出现，且不会出现嵌套。
     *
     * 输入的字符串长度在[1,100]之间。
     *
     *
     *
     * @param args
     */

    @Override
    public void enhancedStrstr(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取源字符串和目标字符串
        String source = scanner.nextLine();
        String target = scanner.nextLine();

        // 将目标字符串中的可选段标记转换为正则表达式的可选字符
        target = target.replaceAll("\\[(.*?)\\]", "[$1]");
        // 编译目标字符串为正则表达式模式
        Pattern pattern = Pattern.compile(target);
        // 创建匹配器，用于在源字符串中查找匹配的子字符串
        Matcher matcher = pattern.matcher(source);
        // 如果找到匹配的子字符串，则输出匹配的子字符串在源字符串中的起始位置
        if (matcher.find()) {
            System.out.println(matcher.start());
        } else {
            // 如果没有找到匹配的子字符串，则输出-1
            System.out.println(-1);
        }



    }

    /**
     * NO. 31分班问题幼儿园分班
     * 儿园两个班的小朋友在排队时混在了一起，每位小朋友都知道自己是否与前面一位小朋友同班，请你帮忙把同班的小朋友找出来。
     *
     * 小朋友的编号是整数，与前一位小朋友同班用Y表示，不同班用N表示。
     *
     * 输入描述
     * 输入为空格分开的小朋友编号和是否同班标志。
     *
     * 比如：6/N 2/Y 3/N 4/Y，表示4位小朋友，2和6同班，3和2不同班，4和3同班。
     *
     * 其中，小朋友总数不超过999，每个小朋友编号大于0，小于等于999。
     *
     * 不考虑输入格式错误问题。
     *
     * 输出描述
     * 输出为两行，每一行记录一个班小朋友的编号，编号用空格分开，且：
     *
     * 编号需按照大小升序排列，分班记录中第一个编号小的排在第一行。
     * 若只有一个班的小朋友，第二行为空行。
     * 若输入不符合要求，则直接输出字符串ERROR。
     * @param args
     */
    @Override
    public void groupKindergarten(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] nums = scanner.nextLine().split(" ");
        String[] start = nums[0].split("/");
        List<String> class_A = new ArrayList<>();
        class_A.add(start[0]);
        List<String> class_B = new ArrayList<>();

        List<List<String>> temp = new ArrayList<>();
        temp.add(class_A);
        temp.add(class_B);
        for (int i = 1; i < nums.length; i++) {
            String[] current = nums[i].split("/");
            String id_ = current[0];
            String f = current[1];

            if (f.equals("Y")) {
                temp = temp;
            } else {
                Collections.reverse(temp);
            }

            temp.get(0).add(id_);
        }
        if (!class_A.isEmpty()) {
            Collections.sort(class_A, (a, b) -> Integer.parseInt(a) - Integer.parseInt(b));
            System.out.println(String.join(" ", class_A));
        }
        if (!class_B.isEmpty()) {
            Collections.sort(class_B, (a, b) -> Integer.parseInt(a) - Integer.parseInt(b));
            System.out.println(String.join(" ", class_B));
        }



    }


    /**
     * NO. 32  战场索敌
     *
     * 有一个大小是N*M的战场地图，被墙壁 ‘#’ 分隔成大小不同的区域，上下左右四个方向相邻的空地 ‘.’ 属于同一个区域，只有空地上可能存在敌人’E”，
     *
     * 请求出地图上总共有多少区域里的敌人数小于K。
     *
     * 输入描述
     * 第一行输入为N,M,K；
     *
     * N表示地图的行数，M表示地图的列数， K表示目标敌人数量
     * N，M<=100
     * 之后为一个NxM大小的字符数组。
     *
     * 输出描述
     * 敌人数小于K的区域数量
     * @param args
     */
    // 定义地图的行数、列数和目标敌人数量
    private static int n, m, k;
    // 定义存储地图的二维字符数组
    private static char[][] matrix;
    // 定义标记访问状态的二维数组
    private static int[][] visited;
    // 记录当前区域的敌人数量
    private static int enemyCount;

    @Override
    public void enemyDetection(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取地图的行数n、列数m和目标敌人数量k
        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();
        // 初始化地图矩阵和访问标记数组
        matrix = new char[n][m];
        visited = new int[n][m];
        // 读取地图矩阵数据
        for (int i = 0; i < n; i++) {
            String row = scanner.next();
            for (int j = 0; j < m; j++) {
                matrix[i][j] = row.charAt(j); // 逐字符读取地图
            }
        }
        int ans = 0; // 初始化符合条件的区域计数
        // 遍历地图中的每个位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果当前格子已经访问过或是墙壁，跳过
                if (visited[i][j] != 0 || matrix[i][j] == '#') {
                    continue;
                }
                enemyCount = 0; // 初始化当前区域的敌人计数
                dfsEnemy(i, j); // 深度优先搜索该区域
                // 如果该区域的敌人数小于k，则该区域符合条件
                ans += enemyCount < k ? 1 : 0;
            }
        }
        // 输出符合条件的区域数量
        System.out.println(ans);
    }

    // 深度优先搜索函数，从(i, j)位置开始计算敌人数
    public static void dfsEnemy(int i, int j) {
        visited[i][j] = 1; // 将当前位置标记为已访问

        // 如果当前位置是敌人，增加敌人计数
        if (matrix[i][j] == 'E') {
            enemyCount++;
        }

        // 定义四个方向的偏移量：上、下、左、右
        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 遍历四个相邻方向
        for (int[] offset : offsets) {
            int newX = i + offset[0];
            int newY = j + offset[1];

            // 检查相邻位置是否在地图范围内，未访问过且不是墙壁
            if (newX >= 0 && newX < n && newY >= 0 && newY < m && visited[newX][newY] == 0 && matrix[newX][newY] != '#') {
                dfsEnemy(newX, newY); // 递归访问相邻位置
            }
        }
    }

    /**
     *  NO. 33  字符串拼接
     *给定 M（0 < M ≤ 30）个字符（a-z），从中取出任意字符（每个字符只能用一次）拼接成长度为 N（0 < N ≤ 5）的字符串，
     *
     * 要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，
     *
     * 输入非法或者无法拼接出满足条件的字符串则返回0。
     *
     * 输入描述
     * 给定的字符列表和结果字符串长度，中间使用空格(" ")拼接
     *
     * 输出描述
     * 满足条件的字符串个数
     *
     * @param args
     */
    @Override
    public void strConcact(String[] args) {
        // 创建一个Scanner对象来读取用户的输入
        Scanner sc = new Scanner(System.in);
        // 读取用户输入的字符串
        String input = sc.nextLine();
        // 将输入的字符串按空格分割为两部分，分别为字符串和长度
        String[] parts = input.split(" ");
        String str = parts[0]; // 获取输入的字符串
        int length = Integer.parseInt(parts[1]); // 将输入的长度部分转换为整数

        // 调用countDistinctStrings方法计算满足条件的不同字符串的数量
        int count = countDistinctStrings(str, length);
        // 输出计算结果
        System.out.println(count);


    }


    // 计算满足条件的不同字符串的数量
    public static int countDistinctStrings(String str, int length) {
        // 创建一个HashSet来存储不同的字符串
        HashSet<String> set = new HashSet<>();
        // 创建一个boolean数组来标记字符串中的字符是否已经被使用
        boolean[] used = new boolean[str.length()];
        // 调用generateDistinctStrings方法生成满足条件的不同字符串
        generateDistinctStrings(str, length, "", set, used);
        // 打印生成的所有不同的字符串
        // for(String str1 : set){
        // System.out.println(str1);
        // }
        // 返回不同字符串的数量
        return set.size();
    }

    // 递归生成满足条件的不同字符串
    public static void generateDistinctStrings(String str, int length, String current, HashSet<String> set, boolean[] used) {
        // 当生成的字符串长度等于指定长度时，将其加入到HashSet中
        if (current.length() == length) {
            set.add(current);
            return;
        }

        // 遍历字符串中的字符
        for (int i = 0; i < str.length(); i++) {
            // 判断字符是否已经被使用，或者当前字符与前一个字符相同
            if (used[i] || (current.length() > 0 && current.charAt(current.length() - 1) == str.charAt(i))) {
                continue; // 如果字符已被使用或与前一个字符相同，则跳过当前字符
            }
            used[i] = true; // 标记当前字符为已使用
            // 递归调用生成下一个字符
            generateDistinctStrings(str, length, current + str.charAt(i), set, used);
            used[i] = false; // 取消标记当前字符的使用状态，以便下一次遍历
        }
    }


    /**
     *  NO. 34  5G网络建设
     * 题目描述
     * 现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N，接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间假设光纤的成本各不相同，且有些节点之间已经存在光纤相连。
     *
     * 请你设计算法，计算出能联通这些基站的最小成本是多少。
     *
     * 注意：基站的联通具有传递性，比如基站A与基站B架设了光纤，基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通。
     *
     * 输入描述
     * 第一行输入表示基站的个数N，其中：
     *
     * 0 < N ≤ 20
     * 第二行输入表示具备光纤直连条件的基站对的数目M，其中：
     *
     * 0 < M < N * (N - 1) / 2
     * 从第三行开始连续输入M行数据，格式为
     *
     * X Y Z P
     *
     * 其中：
     *
     * X，Y 表示基站的编号
     *
     * 0 < X ≤ N
     * 0 < Y ≤ N
     * X ≠ Y
     * Z 表示在 X、Y之间架设光纤的成本
     *
     * 0 < Z < 100
     * P 表示是否已存在光纤连接，0 表示未连接，1表示已连接
     *
     * 输出描述
     * 如果给定条件，可以建设成功互联互通的5G网络，则输出最小的建设成本
     *
     * 如果给定条件，无法建设成功互联互通的5G网络，则输出 -1
     * @param args
     */
    @Override
    public void networkConstruction(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 基站数量（节点数）
        int m = sc.nextInt(); // 基站对数量（边数）


        // 邻接矩阵
        int[][] graph = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 初始化默认各点之间互不联通，即i-j边权无限大
                graph[i][j] = Integer.MAX_VALUE;
            }
        }


        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            int p = sc.nextInt();

            if (p == 0) {
                // x-y边权为z
                graph[x][y] = z;
                graph[y][x] = z;
            } else {
                // 对应已经联通的两点，可以理解为边权为0
                graph[x][y] = 0;
                graph[y][x] = 0;
            }
        }
        System.out.println(prim(graph, n));
    }



    public static int prim(int[][] graph, int n) {
        // 记录最小生成树的边权和
        int minWeight = 0;

        // inTree[i] 表示 节点i 是否在最小生成树中
        boolean[] inTree = new boolean[n + 1];

        // 初始时任选一个节点作为最小生成树的初始节点，这里选择节点1
        inTree[1] = true;
        // 记录最小生成树中点数量
        int inTree_count = 1;

        // dis[i]表示 节点i 到最小生成树集合 的最短距离
        int[] dis = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // 初始时，最小生成树集合中只有节点1，因此其他节点到最小生成树的距离，其实就是到节点1的距离
            dis[i] = graph[1][i];
        }

        // 如果最小生成树中点数量达到n个，则结束循环
        while (inTree_count < n) {
            // 现在我们需要从未纳入最小生成树的点中，找到一个距离最小生成树最近的

            // minDis 记录这个最近距离
            int minDis = Integer.MAX_VALUE;
            // idx 记录距离最小生成树minDis个距离的节点
            int nodeIdx = 0;

            for (int i = 1; i <= n; i++) {
                // 从未纳入最小生成树的点中，找到一个距离最小生成树最近的
                if (!inTree[i] && dis[i] < minDis) {
                    minDis = dis[i];
                    nodeIdx = i;
                }
            }

            // 如果nodeIdx == 0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VALUE，即不与最小生成树存在关联
            if (nodeIdx == 0) {
                // 则说明，当前所有点无法形成最小生成树
                return -1;
            }

            inTree[nodeIdx] = true; // 最小生成树需要纳入最短距离点nodeIdx
            inTree_count++; // 最小生成树中点数量+1
            minWeight += dis[nodeIdx]; // 更新最小生成树的权重和

            // dis[i] 初始时记录的是节点i 到 节点1 的距离（初始的生成树中只有节点1）
            // 现在生成树纳入了新节点nodeIdx，则我们需要更新一下dis[i]，即有可能某些点到最小生成树中的nodeIdx点距离更近
            for (int i = 1; i <= n; i++) {
                if (!inTree[i] && graph[nodeIdx][i] < dis[i]) {
                    // 注意，这是一个累进过程，初始时dis[i]记录的是节点i到节点1的距离，
                    // 之后，最小生成树纳入新点后，如果节点i到新点的距离更近，则dis[i]就更新为这个更短距离
                    // 总之，dis[i] 记录的是 节点 i 到最小生成树的最短距离
                    dis[i] = graph[nodeIdx][i];
                }
            }
        }

        return minWeight;
    }

    /**
     * NO. 35  Excel单元格数值统计
     * Excel工作表中对选定区域的数值进行统计的功能非常实用。
     *
     * 仿照Excel的这个功能，请对给定表格中选中区域中的单元格进行求和统计，并输出统计结果。
     *
     * 为简化计算，假设当前输入中每个单元格内容仅为数字或公式两种。
     *
     * 如果为数字，则是一个非负整数，形如3、77
     *
     * 如果为公式，则固定以=开头，且仅包含下面三种情况：
     *
     * 等于某单元格的值，例如=B12
     * 两个单元格的双目运算（仅为+或-），形如=C1-C2、C3+B2
     * 单元格和数字的双目运算（仅为+或-），形如=B1+1、100-B2
     * 注意：
     *
     * 公式内容都是合法的，例如不存在，=C+1、=C1-C2+B3,=5、=3+5
     * 不存在循环引用，例如A1=B1+C1、C1=A1+B2
     * 内容中不存在空格、括号
     * 输入描述
     * 第一行两个整数rows cols，表示给定表格区域的行数和列数，1<=rows<=20，1<=cols<=26。
     * 接下来rows行，每行cols个以空格分隔的字符串，表示给定表格values的单元格内容。
     * 最后一行输入的字符串，表示给定的选中区域，形如A1:C2。
     *
     * 输出描述
     * 一个整数，表示给定选中区域各单元格中数字的累加总和，范围-2,147,483,648 ~ 2,147,483,647
     *
     * 备注
     * 表格的行号1~20，列号A~Z，例如单元格B3对应values[2][1]。
     * 输入的单元格内容（含公式）中数字均为十进制，值范围[0, 100]。
     * 选中区域：冒号左侧单元格表示选中区域的左上角，右侧表示右下角，如可以为B2:C10、B2:B5、B2:Y2、B2:B2,无类似C2:B2、C2:A1的输入。
     * @param args
     */
    static String[][] table; // 给定表格区域
    static int rows; // 给定表格区域的行数
    static int cols; // 给定表格区域的列数
    static String start; // 选中区域的左上角位置
    static String end; // 选中区域的右下角位置

    @Override
    public void cellStatic(String[] args) {
        Scanner sc = new Scanner(System.in);

        rows = sc.nextInt();
        cols = sc.nextInt();

        table = new String[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                table[i][j] = sc.next();
            }
        }

        String[] range = sc.next().split(":");
        start = range[0];
        end = range[1];

        System.out.println(getResult());
    }

    public static int getResult() {
        int[] s = getPos(start);
        int[] e = getPos(end);

        int r1 = s[0], c1 = s[1];
        int r2 = e[0], c2 = e[1];

        int ans = 0;
        for (int i = r1; i <= r2; i++) {
            for (int j = c1; j <= c2; j++) {
                ans += getCellVal(table[i][j]);
            }
        }

        return ans;
    }


    // 获取单元格的值
    public static int getCellVal(String cell) {
        /*
         * 单元格内容cell如果以'='开头，则必然是公式
         * */
        if (cell.charAt(0) == '=') {
            // fn是公式内容
            String fn = cell.substring(1);

            // 如果公式内容fn包含“+”，则可能是两个单元格的双目运算，也可能是单元格和数字的双目运算
            if (fn.contains("+")) {
                return operate(fn.split("\\+"), true);
            }
            // 如果公式内容fn包含“-”，则可能是两个单元格的双目运算，也可能是单元格和数字的双目运算
            else if (fn.contains("-")) {
                return operate(fn.split("-"), false);
            }
            // 如果公式内容fn不包含“+”和“-”，则必然等于某单元格的值，例如=B12
            else {
                return getPosVal(getPos(fn));
            }
        }
        /*
         * 单元格内容cell如果不以'='开头，则必然是数字，且是非负正数
         * */
        else {
            return Integer.parseInt(cell);
        }
    }

    // 双目运算
    public static int operate(String[] ops, boolean isAdd) {
        int op1, op2;

        if (isPos(ops[0])) {
            // 如果操作数1是单元格
            op1 = getPosVal(getPos(ops[0]));
        } else {
            // 如果操作数1是数字
            op1 = Integer.parseInt(ops[0]);
        }

        if (isPos(ops[1])) {
            // 如果操作数2是单元格
            op2 = getPosVal(getPos(ops[1]));
        } else {
            // 如果操作数2是数字
            op2 = Integer.parseInt(ops[1]);
        }

        if (isAdd) {
            // 加法运算
            return op1 + op2;
        } else {
            // 减法运算
            return op1 - op2;
        }
    }

    // 解析单元格坐标  为  矩阵坐标
    public static int[] getPos(String pos) {
        int c = pos.charAt(0) - 65;
        int r = Integer.parseInt(pos.substring(1)) - 1;
        return new int[] {r, c};
    }

    // 获取矩阵对应坐标的值，并且更新矩阵对应单元格的内容
    public static int getPosVal(int[] pos) {
        int r = pos[0], c = pos[1];
        int val = getCellVal(table[r][c]);
        table[r][c] = val + "";
        return val;
    }

    // 判断一个内容是否为单元格坐标
    public static boolean isPos(String str) {
        char c = str.charAt(0);
        return c <= 'Z' && c >= 'A';
    }


    /**
     * NO. 36  欢乐的周末
     * 小华和小为是很要好的朋友，他们约定周末一起吃饭。
     *
     * 通过手机交流，他们在地图上选择了多个聚餐地点（由于自然地形等原因，部分聚餐地点不可达），求小华和小为都能到达的聚餐地点有多少个？
     *
     * 输入描述
     * 第一行输入 m 和 n
     *
     * m 代表地图的长度
     * n 代表地图的宽度
     * 第二行开始具体输入地图信息，地图信息包含：
     *
     * 0 为通畅的道路
     * 1 为障碍物（且仅1为障碍物）
     * 2 为小华或者小为，地图中必定有且仅有2个 （非障碍物）
     * 3 为被选中的聚餐地点（非障碍物）
     *
     *
     * @param args
     */
    @Override
    public void happyWeekEnd(String[] args) {

        Scanner sc = new Scanner(System.in);

        // 长度m表示行数
        int m = sc.nextInt();
        // 宽度n表示列数
        int n = sc.nextInt();

        int[][] matrix = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        UnionFindSet ufs = new UnionFindSet(rows * cols);

        // 记录小华，小为的位置
        ArrayList<Integer> huawei = new ArrayList<>();
        // 记录餐厅的位置
        ArrayList<Integer> restaurants = new ArrayList<>();

        // 上下左右四个方向偏移量
        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != 1) {
                    // 二维坐标(i, j) 转为 一维坐标pos
                    int pos = i * cols + j;

                    if (matrix[i][j] == 2) {
                        // 收集小华，小为的位置
                        huawei.add(pos);
                    } else if (matrix[i][j] == 3) {
                        // 收集餐厅的位置
                        restaurants.add(pos);
                    }

                    for (int[] offset : offsets) {
                        int newI = i + offset[0];
                        int newJ = j + offset[1];
                        if (newI >= 0 && newI < rows && newJ >= 0 && newJ < cols && matrix[newI][newJ] != 1) {
                            // 如果(i,j)和（newI,newJ）位置都是非1，则合并
                            ufs.union(pos, newI * cols + newJ);
                        }
                    }
                }
            }
        }

        // 小华所在连通分量的根
        int hua_fa = ufs.find(huawei.get(0));
        // 小为所在连通分量的根
        int wei_fa = ufs.find(huawei.get(1));
// 如果小华和小为的不属于同一个连通分量，则二人无法去往相同餐厅
        if (hua_fa != wei_fa) {
            System.out.println(0);
        }
        // 找出和小华、小为在同一个连通分量里面的餐厅
        int ans = 0;
        for (Integer restaurant : restaurants) {
            if (ufs.find(restaurant) == hua_fa) {
                ans++;
            }
        }
        System.out.println(ans);

    }

    /**
     * NO. 37  计算误码率
     *题目描述
     * 误码率是最常用的数据通信传输质量指标。它可以理解为“在多少位数据中出现一位差错”。
     *
     * 移动通信网络中的误码率主要是指比特误码率，其计算公式如下: 比特误码率=错误比特数/传输总比特数，
     *
     * 为了简单，我们使用字符串来标识通信的信息，一个字符错误了，就认为出现了一个误码
     *
     * 输入一个标准的字符串，和一个传输后的字符串，计算误码率
     *
     * 字符串会被压缩，
     * 例:“2A3B4D5X1Z”表示"AABBBDDDDXXXXXZ"
     * 用例会保证两个输入字符串解压后长度一致，解压前的长度不一定一致
     *
     * 每个生成后的字符串长度<100000000。
     *
     * 输入描述
     * 两行，分别为两种字符串的压缩形式。
     *
     * 每行字符串 (压缩后的) 长度<100000
     *
     * 输出描述
     * 一行，错误的字等数量/展开后的总长度
     *
     * 备注
     * 注意：展开后的字符串不含数字
     *
     *
     * @param args
     */
    @Override
    public void calculateErrorRate(String[] args) {
        Scanner sc = new Scanner(System.in);

        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        LinkedList<ZipStr> link1 = getZipStrLink(s1);
        LinkedList<ZipStr> link2 = getZipStrLink(s2);
        int diff = 0;
        int same = 0;
        while (link1.size() > 0) {
            ZipStr zipStr1 = link1.removeFirst();
            ZipStr zipStr2 = link2.removeFirst();
            int compareCount = Math.min(zipStr1.getNum(), zipStr2.getNum());
            if (zipStr1.getC() != zipStr2.getC()) {
                diff += compareCount;
            } else {
                same += compareCount;
            }
            if (zipStr1.getNum() > compareCount) {
                zipStr1.setNum(zipStr1.getNum() -compareCount); ;
                link1.addFirst(zipStr1);
                continue;
            }

            if (zipStr2.getNum() > compareCount) {
                zipStr2.setNum(zipStr2.getNum() -compareCount) ;
                link2.addFirst(zipStr2);
            }
        }

        System.out.println( diff + "/" + (diff + same));

    }

    public static LinkedList<ZipStr> getZipStrLink(String s) {
        LinkedList<ZipStr> link = new LinkedList<>();

        StringBuilder num = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c >= '0' && c <= '9') {
                num.append(c);
            } else {
                link.add(new ZipStr(Integer.parseInt(num.toString()), c));
                num = new StringBuilder();
            }
        }

        return link;
    }

    /**
     * NO. 38  简易内存池
     * 题目描述
     * 请实现一个简易内存池,根据请求命令完成内存分配和释放。
     * 内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
     * REQUEST=请求的内存大小 表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
     * RELEASE=释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
     * 注意：
     *
     * 内存池总大小为100字节。
     * 内存池地址分配必须是连续内存，并优先从低地址分配。
     * 内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。
     * 不会释放已申请的内存块的中间地址。
     * 释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。
     * 输入描述
     * 首行为整数 N , 表示操作命令的个数，取值范围：0 < N <= 100。
     *
     * 接下来的N行, 每行将给出一个操作命令，操作命令和参数之间用 “=”分割。
     *
     * 输出描述
     * 请求分配指定大小内存时，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error
     *
     * 释放掉之前分配的内存时，释放成功无需输出，如果释放不存在的首地址则输出error。
     * @param args
     */
    @Override
    public void simpleMemoryPool(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        String[][] cmds = new String[n][2];
        for (int i = 0; i < n; i++) cmds[i] = sc.next().split("=");

        // used保存被占用的内存 [起始地址，结束地址]，初始时有一个[100,101]作为尾边界限定
        LinkedList<Integer[]> used = new LinkedList<>();
        used.add(new Integer[] {100, 101});

        for (String[] cmd : cmds) {
            String key = cmd[0];
            String val = cmd[1];
            if ("REQUEST".equals(key)) {

                // 当指令为REQUEST时，对应值为要申请的内存的大小，即size
                int size = Integer.parseInt(val);
                // 我们默认从start=0位置开始检查可用内存区间
                int start = 0;
                boolean flag = true;
                for (int i = 0; i < used.size(); i++) {
                    int end = start + size - 1;
                    // 要申请的内存区间
                    Integer[] range = {start, end};

                    // 检查要申请的内存区间和已占有的内存区间是否交叉
                    if (!hasIntersection(used.get(i), range)) {
                        // 若不存在交叉，则将申请区间加入used中
                        used.add(i, range);
                        flag = false;
                        // 并打印此时申请区间的起始位置
                        System.out.println(start);
                        break;
                    } else {
                        // 若存在交叉，则将变更要申请的内存区间的起始位置
                        start = used.get(i)[1] + 1;
                    }
                }

                // 一旦申请到内存，那么flag就会被赋值为false，否则就保持true，意味着每申请到内存，则打印error
                if (flag) System.out.println("error");

            }else{

                //  当指令为RELEASE时，值为要释放内存的起始地址addr
                int addr = Integer.parseInt(val);
                boolean flag = true;

                for (int i = 0; i < used.size(); i++) {
                    // 到已占有内存中找起始位置是addr的，找到则将该区间从used中删除，表示解除占用
                    if (used.get(i)[0] == addr) {
                        used.remove(i);
                        flag = false;
                        break;
                    }
                }

                // 一旦释放成功，则flag就会被置为false，否则就保持True,意味着没有内存释放，则打印error
                if (flag) System.out.println("error");

            }


        }



    }

    // 判断两个区间是否存在交集
    public static boolean hasIntersection(Integer[] range1, Integer[] range2) {
        int s1 = range1[0];
        int e1 = range1[1];

        int s2 = range2[0];
        int e2 = range2[1];

        if (s1 == s2) return true;
        else if (s1 < s2) return e1 >= s2;
        else return e2 >= s1;
    }

    /**
     * NO. 39  抢7游戏
     * A、B两个人玩抢7游戏，游戏规则为：
     *
     * A先报一个起始数字 X（10 ≤ 起始数字 ≤ 10000），B报下一个数字 Y （X - Y < 3），A再报一个数字 Z（Y - Z < 3），以此类推，直到其中一个抢到7，抢到7即为胜者；
     *
     * 在B赢得比赛的情况下，一共有多少种组合？
     *
     * 输入描述
     * 起始数字 M
     *
     * 10 ≤ M ≤ 10000
     * 如：
     *
     * 100
     *
     * 输出描述
     * B能赢得比赛的组合次数
     * @param args
     */
    @Override
    public void LootSevenGame(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        BigInteger[]  factor =  initFactor(m - 7);
        int oneCount = m - 7;
        int twoCount = 0;
        // 记录B赢的情况数
        BigInteger ans = new BigInteger("0");
        while (oneCount >= 0) {
            // 叫的次数为奇数时，才能B赢
            if ((oneCount + twoCount) % 2 != 0) {
                ans = ans.add(getPermutationCount(factor,oneCount, twoCount));
            }

            // 合并两个1为一个2
            oneCount -= 2;
            twoCount += 1;
        }

        System.out.println(ans);

    }


    // 求解不重复的全排列数
    public static BigInteger getPermutationCount( BigInteger[] factor,  int oneCount, int twoCount) {
        if (oneCount == 0 || twoCount == 0) { // 即 1 1 1 1 1 或 2 2 2 这种情况，此时只有一种排列
            return new BigInteger("1");
        } else {
            // 排列数去重，比如 1 1 1 2 2 的不重复排列数为 5! / 3! / 2! = 10
            return factor[oneCount + twoCount].divide(factor[oneCount].multiply(factor[twoCount]));
        }
    }


    // 阶乘
    public static BigInteger[]  initFactor(int n) {
        BigInteger[]  factor = new BigInteger[n + 1];
        factor[0] = new BigInteger("1");
        for (int i = 1; i <= n; i++) {
            factor[i] = factor[i - 1].multiply(new BigInteger(i + ""));
        }
        return factor;
    }

    /**
     * NO. 40  区间交集
     * 给定一组闭区间，其中部分区间存在交集。
     *
     * 任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为[3,5])。
     *
     * 公共区间之间若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。
     *
     * 按升序排列输出合并后的区间列表。
     *
     * 输入描述
     * 一组区间列表，
     *
     * 区间数为 N: 0<=N<=1000;
     *
     * 区间元素为 X: -10000<=X<=10000。
     *
     * 输出描述
     * 升序排列的合并区间列表
     *
     * 备注
     * 区间元素均为数字，不考虑字母、符号等异常输入。
     * 单个区间认定为无公共区间。
     * @param args
     */
    @Override
    public void intervalIntersection(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[][] ranges = new int[n][2];
        for (int i = 0; i < n; i++) {
            ranges[i][0] = sc.nextInt();
            ranges[i][1] = sc.nextInt();
        }
// 区间按照开始位置升序
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);

        // combine用于保存交集
        ArrayList<int[]> combine = new ArrayList<>();

        // 求任意两个区间之间的交集
        for (int i = 0; i < n; i++) {
            int s1 = ranges[i][0], e1 = ranges[i][1];
            for (int j = i + 1; j < n; j++) {
                int s2 = ranges[j][0], e2 = ranges[j][1];
                if (s2 <= e1) {
                    combine.add(new int[] {s2, Math.min(e1, e2)});
                } else {
                    // 由于ranges已经升序，因此如果ranges[i]和ranges[j]没有交集的话，则也不可能和ranges[j+1]区间有交集
                    break;
                }
            }
        }

        if (combine.size() == 0) {
            System.out.println("None");
            return;
        }

        // 合并公共区间
        combine.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);

        int[] pre = combine.get(0);
        for (int i = 1; i < combine.size(); i++) {
            int[] cur = combine.get(i);

            if (pre[1] >= cur[0]) {
                pre[1] = Math.max(cur[1], pre[1]);
            } else {
                System.out.println(pre[0] + " " + pre[1]);
                pre = cur;
            }
        }

        System.out.println(pre[0] + " " + pre[1]);


    }

    /**
     *  NO. 41  士兵过河
     *一支N个士兵的军队正在趁夜色逃亡，途中遇到一条湍急的大河。
     * 敌军在T的时长后到达河面，没到过对岸的士兵都会被消灭。
     * 现在军队只找到了1只小船，这船最多能同时坐上2个士兵。
     *
     * 当1个士兵划船过河，用时为 a[i]；0 <= i < N
     * 当2个士兵坐船同时划船过河时，用时为max(a[j],a[i])两士兵中用时最长的。
     * 当2个士兵坐船1个士兵划船时，用时为 a[i]*10；a[i]为划船士兵用时。
     * 如果士兵下河游泳，则会被湍急水流直接带走，算作死亡。
     * 请帮忙给出一种解决方案，保证存活的士兵最多，且过河用时最短。
     *
     * 输入描述
     * 第一行：N 表示士兵数(0<N<1,000,000)
     * 第二行：T 表示敌军到达时长(0 < T < 100,000,000)
     * 第三行：a[0] a[1] … a[i]… a[N- 1]
     * a[i]表示每个士兵的过河时长。
     * (10 < a[i]< 100; 0<= i< N）
     *
     * 输出描述
     * 第一行：”最多存活士兵数” “最短用时”
     * 备注
     * 1）两个士兵的同时划船时，如果划速不同则会导致船原地转圈圈；所以为保持两个士兵划速相同，则需要向划的慢的士兵看齐。
     * 2）两个士兵坐船时，重量增加吃水加深，水的阻力增大；同样的力量划船速度会变慢；
     * 3）由于河水湍急大量的力用来抵消水流的阻力，所以2）中过河用时不是a[i] *2，
     * 而是a[i] * 10。
     *
     * @param args
     */
    @Override
    public void crossRiver(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int limit = sc.nextInt();

        int[] times = new int[n];

        for (int i = 0; i < n; i++) {
            times[i] = sc.nextInt();
        }

        // 过河时间升序
        Arrays.sort(times);

        // 最少成功过河人数
        int min = 0;
        // 最多成功过河人数
        int max = n;

        // 记录题解
        String ans = "";
        // 二分法取可能成功的过河人数
        while (min <= max) {
            // mid是过河人数
            int mid = (min + max) / 2;
            // 计算mid个人过河所需的最短时间need
            int need = getMinCrossRiverTime(mid, Arrays.copyOfRange(times, 0, mid));
            // 如果need超过了过河时间上限limit，那么说明能成功过河的人没这么多
            if (need > limit) {
                max = mid - 1;
            } else if (need < limit) {
                // 如果need小于过河时间上限limit，那么说明mid个最快的人可以在limit时间内成功过河
                ans = mid + " " + need;
                // 但是可能还可以过更多人
                min = mid + 1;
            } else {
                // 如果need == limit，那么说明过河人数刚好可以在limit时间内成功过河，此时可以直接返回
                ans = mid + " " + need;
                break;
            }
        }

        System.out.println(ans);


    }


    // 计算将n个人运到河对岸所需要花费的最少时间
    public static int getMinCrossRiverTime(int n, int[] t) {
        int cost = 0;

        while (n > 0) {
            if (n == 1) {
                cost += t[0];
                break;
            } else if (n == 2) {
                cost += t[1];
                break;
            } else if (n == 3) {
                cost += t[1] + t[0] + t[2];
                break;
            } else {
                cost += Math.min(t[n - 1] + t[0] + t[n - 2] + t[0], t[1] + t[0] + t[n - 1] + t[1]);
                n -= 2;
            }
        }

        return cost;
    }



    /**
     * NO. 42  书籍叠放
     * 题目描述
     * 书籍的长、宽都是整数对应 (l,w)。如果书A的长宽度都比B长宽大时，则允许将B排列放在A上面。现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个规格书籍能叠放在一起。
     *
     * 输入描述
     * 输入：books = [[20,16],[15,11],[10,10],[9,10]]
     *
     * 说明：总共4本书籍，第一本长度为20宽度为16；第二本书长度为15宽度为11，依次类推，最后一本书长度为9宽度为10.
     *
     * 输出描述
     * 输出：3
     *
     * 说明: 最多3个规格的书籍可以叠放到一起, 从下到上依次为: [20,16],[15,11],[10,10]
     * @param args
     */
    @Override
    public void stackBooks(String[] args) {
        Scanner sc = new Scanner(System.in);

        String input = sc.nextLine();
        // (?<=]),(?=\[) 正则表达式含义是：找这样一个逗号，前面跟着]，后面跟着[
        // 其中(?<=) 表示前面跟着
        // 其中(?=) 表示后面跟着
        Integer[][] books =
                Arrays.stream(input.substring(1, input.length() - 1).split("(?<=]),(?=\\[)"))
                        .map(
                                s ->
                                        Arrays.stream(s.substring(1, s.length() - 1).split(","))
                                                .map(Integer::parseInt)
                                                .toArray(Integer[]::new))
                        .toArray(Integer[][]::new);

        // 长度升序，若长度相同，则宽度降序
        Arrays.sort(books, (a, b) -> Objects.equals(a[0], b[0]) ? b[1] - a[1] : a[0] - b[0]);

        Integer[] widths = Arrays.stream(books).map(book -> book[1]).toArray(Integer[]::new);

        //  dp数组元素dp[i]含义是：长度为i+1的最优子序列的尾数
        ArrayList<Integer> dp = new ArrayList<>();
        dp.add(widths[0]);
        for (int i = 1; i < widths.length; i++) {
            if (widths[i] > dp.get(dp.size() - 1)) {
                dp.add(widths[i]);
                continue;
            }
            if (widths[i] < dp.get(0)) {
                dp.set(0, widths[i]);
                continue;
            }
            int idx = Collections.binarySearch(dp, widths[i]);
            if (idx < 0) dp.set(-idx - 1, widths[i]);


        }
        System.out.println(dp.size());

    }


    /**
     * NO. 43  贪吃的猴子
     *
     * 一只贪吃的猴子，来到一个果园，发现许多串香蕉排成一行，每串香蕉上有若干根香蕉。每串香蕉的根数由数组numbers给出。
     *
     * 猴子获取香蕉，每次都只能从行的开头或者末尾获取，并且只能获取N次，求猴子最多能获取多少根香蕉。
     *
     * 输入描述
     * 第一行为数组numbers的长度
     *
     * 第二行为数组numbers的值每个数字通过空格分开
     *
     * 第三行输入为N，表示获取的次数
     *
     * 输出描述
     * 按照题目要求能获取的最大数值
     *
     * 备注
     * 1 ≤ numbers.length ≤ 100000
     * 1 ≤ numbers ≤ 100
     * 1 ≤ N ≤ numbers.length
     * @param args
     */
    @Override
    public void greedyMonkey(String[] args) {
        Scanner sc = new Scanner(System.in);

        int len = Integer.parseInt(sc.nextLine());
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = Integer.parseInt(sc.nextLine());
        // 初始时，左边选择0个，因此左边选择的香蕉数为 0
        int leftSum = 0;
        // 初始时，右边选择n个，因此右边选择的香蕉数为 nums[len-n] ~ nums[len - 1] 这个n个元素之和
        int rightSum = 0;
        for (int i = len - n; i < len; i++) {
            rightSum += nums[i];
        }
        // 如果选择数n == len，即全选，此时直接返回初始rightSum
        if (len == n) {
            System.out.println(rightSum);
            return ;
        }
        // 如果不是全选
        // sum记录当前选择结果
        int sum = leftSum + rightSum;
        // ans记录所有选择结果中最大的
        int ans = sum;
        // l指向左边将要获得的，即左边获得一个
        int l = 0;
        // r指向右边将要失去的，即右边失去一个
        int r = len - n;
        while (l < n) {
            sum += nums[l++] - nums[r++];
            ans = Math.max(ans, sum);
        }

        System.out.println(ans);
    }

    /**
     * NO. 44   贪心歌手
     * 一个歌手准备从A城去B城参加演出。
     *
     * 按照合同，他必须在 T 天内赶到
     * 歌手途经 N 座城市
     * 歌手不能往回走
     * 每两座城市之间需要的天数都可以提前获知。
     * 歌手在每座城市都可以在路边卖唱赚钱。
     *
     * 经过调研，歌手提前获知了每座城市卖唱的收入预期：
     * 如果在一座城市第一天卖唱可以赚M，后续每天的收入会减少D（第二天赚的钱是 M - D，第三天是 M - 2D ...）。如果收入减少到 0 就不会再少了。
     * 歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。
     * 贪心的歌手最多可以赚多少钱？
     *
     * 输入描述
     * 第一行两个数字 T 和 N，中间用空格隔开。
     *
     * T 代表总天数，0 < T < 1000
     * N 代表路上经过 N 座城市，0 < N < 100
     * 第二行 N+1 个数字，中间用空格隔开。代表每两座城市之间耗费的时间。
     *
     * 其总和 ≤ T。
     * 接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的输入预期。
     *
     * 0 < M < 1000
     * 0 < D < 100
     * 输出描述
     * 一个数字。代表歌手最多可以赚多少钱。以回车结束。
     *
     * @param args
     */
    static int time;
    static int num;
    static int roadCost;
    static int[][] mds;
    @Override
    public void greedySinger(String[] args) {

        Scanner sc = new Scanner(System.in);

        time = sc.nextInt();
        num = sc.nextInt();

        // roadCost是A~B城市必需的路程时间
        roadCost = 0;

        for (int i = 0; i < n + 1; i++) {
            roadCost += sc.nextInt();
        }

        mds = new int[n][2];
        for (int i = 0; i < n; i++) {
            mds[i][0] = sc.nextInt();
            mds[i][1] = sc.nextInt();
        }
        // remain是刨去必要的路程时间后，剩余可以用于赚钱的时间
        int remain = time - roadCost;
        // 如果没有剩余时间可以用，则赚不到钱
        if (remain <= 0) {
            System.out.println(0);
            return ;
        }
        // 优先队列（小顶堆）记录赚到的钱, 即堆顶是某天赚的最少的钱
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);
        for (int[] md : mds) {

            // 第一天卖唱可以赚m，后续每天的收入会减少d
            int m = md[0];
            int d = md[1];
            // 只要在当前城市还有钱赚，那么就继续待
            while (m > 0) {
                // 只有remain天可以赚钱，超出的时间不能赚钱，因此需要比较超出的时间赚的钱m，和前面时间中赚的最少的钱pq.peek
                if (pq.size() >= remain){
                    // pq.peek只可能是某座城市停留的最后一天的赚的钱，因为每座城市都是停留的最后一天赚的钱最少
                    if (m > pq.peek()) {
                        // 如果当前城市当天赚的钱m，比前面天里面赚的最少的pq.peek多，那么就赚pq.peek钱的那天时间节约下来，给当天用
                        pq.poll();
                    }else{
                        // 如果当前城市当天赚的钱m，比前面天里面赚的最少的pq.peek还少，则当前城市继续待下去赚的钱只会更少，因此没必要呆下去了
                        break;
                    }
                }
                // 如果所有城市停留时间没有超出remain天，或者当天是超出的时间，但是比前面赚的最少的一天的赚的更多，则赚m更优
                pq.add(m);
                //  每天收入减少d
                m -= d;
            }

        }

        System.out.println( pq.stream().reduce(Integer::sum).orElse(0));


    }

    /**
     * NO. 45   无向图染色
     * 题目描述
     * 给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？
     *
     * 输入描述
     * 第一行输入M(图中节点数) N(边数)
     *
     * 后续N行格式为：V1 V2表示一个V1到V2的边。
     *
     * 数据范围：1 <= M <= 15,0 <= N <= M * 3，不能保证所有节点都是连通的。
     *
     * 输出描述
     * 输出一个数字表示染色方案的个数。
     *
     * @param args
     */
    @Override
    public void undirectedGraphColoring(String[] args) {

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        int[][] edges = new int[n][2];
        for (int i = 0; i < n; i++) {
            edges[i][0] = sc.nextInt();
            edges[i][1] = sc.nextInt();
        }
        // connect用于存放每个节点的相邻节点
        HashMap<Integer, HashSet<Integer>> connect = new HashMap<>();

        for (int[] edge : edges) {
            connect.putIfAbsent(edge[0], new HashSet<>());
            connect.get(edge[0]).add(edge[1]);

            connect.putIfAbsent(edge[1], new HashSet<>());
            connect.get(edge[1]).add(edge[0]);
        }

        // 节点从index=1开始，必有count=1个的全黑染色方案
        System.out.println(dfs(connect, m, 1, 1, new LinkedList<>()));

    }


    // 该方法用于求解给定多个节点染红的全组合数
    public static int dfs(HashMap<Integer, HashSet<Integer>> connect,int m, int index, int count,
                          LinkedList<HashSet<Integer>> path) {
        if (path.size() == m) return count;

        outer:
        for (int i = index; i <= m; i++) {
            // 如果新加入节点i和已有节点j相邻，则说明新加入节点不能染成红色，需要进行剪枝
            for (HashSet<Integer> p : path) {
                if (p.contains(i)) continue outer;
            }

            count++;

            if (connect.containsKey(i)) {
                path.addLast(connect.get(i));
                count = dfs(connect, m, i + 1, count, path);
                path.removeLast();
            } else {
                count = dfs(connect, m, i + 1, count, path);
            }
        }

        return count;
    }


    /**
     * NO. 46   最小循环子数组
     * 给定一个由若干整数组成的数组nums，请检查数组是否是由某个子数组重复循环拼接而成，请输出这个最小的子数组。
     *
     * 输入描述
     * 第一行输入数组中元素个数n，1 ≤ n ≤ 100000
     *
     * 第二行输入数组的数字序列nums，以空格分割，0 ≤ nums[i] < 10
     *
     * 输出描述
     * 输出最小的子数组的数字序列，以空格分割；
     *
     * 备注
     * 数组本身是其最大的子数组，循环1次可生成的自身；
     *
     *
     *
     * @param args
     */
    @Override
    public void minCycleSubArray(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // KMP算法 前缀表求解
        int[] next = getNext(n, nums);
        // 最长相同前后缀长度
        int m = next[n - 1];
// 最小重复子串的长度
        int len = n % (n - m) == 0 ? n - m : n;
        StringJoiner sj = new StringJoiner(" ");
        for (int i = 0; i < len; i++) sj.add(nums[i] + "");
        System.out.println(sj.toString());
    }





    public static int[] getNext(int n, int[] nums) {
        int[] next = new int[n];

        int j = 1;
        int k = 0;

        while (j < n) {
            if (nums[j] == nums[k]) {
                next[j] = k + 1;
                j++;
                k++;
            } else {
                if (k > 0) {
                    k = next[k - 1];
                } else {
                    j++;
                }
            }
        }

        return next;
    }



    /**
     * NO. 47   最长的顺子
     * 斗地主起源于湖北十堰房县，据说是一位叫吴修全的年轻人根据当地流行的扑克玩法“跑得快”改编的，如今已风靡整个中国，并流行于互联网上。
     *
     * 牌型：单顺，又称顺子，最少5张牌，最多12张牌(3…A)不能有2，也不能有大小王，不计花色。
     *
     * 例如： 3-4-5-6-7-8，7-8-9-10-J-Q，3-4-5-6-7-8-9-10-J-Q-K-A
     *
     * 可用的牌 3<4<5<6<7<8<9<10<J<Q<K<A<2<B(小王)<C(大王)，每种牌除大小王外有四种花色
     *
     * (共有13×4+2张牌)
     *
     * 输入：
     *
     * 手上有的牌
     * 已经出过的牌(包括对手出的和自己出的牌)
     * 输出：
     *
     * 对手可能构成的最长的顺子(如果有相同长度的顺子，输出牌面最大的那一个)，
     * 如果无法构成顺子，则输出 NO-CHAIN。
     * 输入描述
     * 输入的第一行为当前手中的牌
     *
     * 输入的第二行为已经出过的牌
     *
     * 输出描述
     * 最长的顺子
     * @param args
     */
    @Override
    public void longestSequence(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] my = sc.nextLine().split("-");
        String[] used = sc.nextLine().split("-");
        // 牌面值 映射为 count列表索引值
        HashMap<String, Integer> mapToV = new HashMap<>();
        mapToV.put("3", 3);
        mapToV.put("4", 4);
        mapToV.put("5", 5);
        mapToV.put("6", 6);
        mapToV.put("7", 7);
        mapToV.put("8", 8);
        mapToV.put("9", 9);
        mapToV.put("10", 10);
        mapToV.put("J", 11);
        mapToV.put("Q", 12);
        mapToV.put("K", 13);
        mapToV.put("A", 14);
        mapToV.put("2", 16);
        mapToV.put("B", 17);
        mapToV.put("C", 18);
        // count每个索引值对应一个牌面值，count元素值就是对应牌面的数量
        // 牌面值             3  4  5  6  7  8  9  10 J  Q  K  A     2  B  C
        // 索引值             3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
        int[] count = {0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 1, 1};
        // count列表索引值 隐射为 牌面值
        HashMap<Integer, String> mapToK = new HashMap<>();
        mapToK.put(3, "3");
        mapToK.put(4, "4");
        mapToK.put(5, "5");
        mapToK.put(6, "6");
        mapToK.put(7, "7");
        mapToK.put(8, "8");
        mapToK.put(9, "9");
        mapToK.put(10, "10");
        mapToK.put(11, "J");
        mapToK.put(12, "Q");
        mapToK.put(13, "K");
        mapToK.put(14, "A");
        mapToK.put(16, "2");
        mapToK.put(17, "B");
        mapToK.put(18, "C");

        // 总牌数 减去 自己手中牌数
        for (String k : my) {
            count[mapToV.get(k)] -= 1;
        }

        // 总牌数 减去 已打出去的牌数
        for (String k : used) {
            count[mapToV.get(k)] -= 1;
        }
        String ans = "NO-CHAIN";
        int maxLen = 0;
        // l为顺子的左边界，[3,10]，即顺子的左边界值最少是count索引3，最多是count索引10
        int l = 3;
        while (l <= 10) {
            ArrayList<String> tmp = new ArrayList<>();
            StringJoiner sj = new StringJoiner("-");
            for (int r = l; r < 16; r++) {
                // 如果对应牌数>=1，则可以组顺子
                if (count[r] >= 1) {
                    tmp.add(mapToK.get(r));
                    sj.add(mapToK.get(r));
                } else {
                    // 如果对应牌数 == 0，则顺子中断
                    // 顺子必须大于五张牌，且总是记录最长，遇到长度相同的，记录后面发现的顺子
                    if (tmp.size() >= 5 && tmp.size() >= maxLen) {
                        maxLen = tmp.size();
                        ans = sj.toString();
                    }
                    // 顺子中断处+1，即为下一次顺子的起始位置
                    l = r;
                    break;
                }
            }
            l++;
        }
        System.out.println(ans);
    }

    /**
     * NO. 48   数组组成的最小数字
     * @param args
     * 给定一个整型数组，请从该数组中选择3个元素组成最小数字并输出（如果数组长度小于3，则选择数组中所有元素来组成最小数字）
     *
     * 输入描述
     * 一行用半角逗号分割的字符串记录的整型数组，0 < 数组长度 <= 100，0 < 整数的取值范围 <= 10000
     *
     * 输出描述
     * 由3个元素组成的最小数字，如果数组长度小于3，则选择数组中所有元素来组成最小数字
     */
    @Override
    public void smallestNumber(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strs = sc.nextLine().split(","); // 读取输入并按逗号分割
        // 先按照数值大小排序，并取最小的 3 个元素
        List<String> sortedList = Arrays.stream(strs)
                .sorted(Comparator.comparingInt(Integer::parseInt)) // 数值排序
                .limit(3) // 取最小的 3 个元素
                .sorted((a, b) -> (a + b).compareTo(b + a)) // 按拼接结果排序
                .collect(Collectors.toList());
        System.out.println(String.join("", sortedList)); // 计算结果并输出

    }

    /**
     * NO. 49   荒岛求生
     * 一个荒岛上有若干人，岛上只有一条路通往岛屿两端的港口，大家需要逃往两端的港口才可逃生。
     *
     * 假定每个人移动的速度一样，且只可选择向左或向右逃生。
     *
     * 若两个人相遇，则进行决斗，战斗力强的能够活下来，并损失掉与对方相同的战斗力；若战斗力相同，则两人同归于尽。
     *
     * 输入描述
     * 给定一行非 0 整数数组，元素个数不超过30000；
     *
     * 正负表示逃生方向（正表示向右逃生，负表示向左逃生），绝对值表示战斗力，越左边的数字表示里左边港口越近，逃生方向相同的人永远不会发生决斗。
     *
     * 输出描述
     * 能够逃生的人总数，没有人逃生输出0，输入异常时输出-1
     *
     *
     * @param args
     */
    @Override
    public void StrandedDeep(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取一行输入，并使用空格分隔字符串
        String[] input = scanner.nextLine().split(" ");

        // 创建一个整数列表，用于存储输入的整数
        List<Integer> people = new ArrayList<>();

        // 将输入的字符串数组转换为整数，并添加到people列表中
        for (String s : input) {
            people.add(Integer.parseInt(s));
        }
        // 如果people列表的大小大于30000，则输出-1
        if (people.size() > 30000) {
            System.out.println(-1);
        } else {
            // 调用asteroidCollision方法，并将结果输出
            int result = asteroidCollision(people);
            System.out.println(result);
        }



    }


    // 定义一个名为asteroidCollision的方法，接受一个整数列表作为参数
    public static int asteroidCollision(List<Integer> people) {
        // 创建一个新的ArrayList，用于存储幸存者
        List<Integer> survivors = new ArrayList<>();
        // 遍历输入的整数列表
        for (int person : people) {

            // 如果person等于0，则返回-1
            if (person == 0) {
                return -1;
            }

            // 初始化一个布尔变量alive为true
            boolean alive = true;

            // 当alive为true且person小于0，且survivors不为空，且survivors列表中最后一个元素大于0时，执行循环
            while (alive && person < 0 && !survivors.isEmpty() && survivors.get(survivors.size() - 1) > 0) {
                // 更新alive的值，判断当前person是否比survivors列表中最后一个元素的相反数大
                alive = survivors.get(survivors.size() - 1) < -person;
                // 如果survivors列表中最后一个元素小于等于person的相反数，则移除该元素
                if (survivors.get(survivors.size() - 1) <= -person) {
                    person = person + survivors.get(survivors.size() - 1);
                    survivors.remove(survivors.size() - 1);
                }
                // 如果alive为true，则将person添加到survivors列表中
                if (alive) {
                    survivors.add(person);
                }
            }


        }
        // 返回survivors列表的大小
        return survivors.size();

    }

    /**
     * NO. 50   整理扑克牌
     *给定一组数字，表示扑克牌的牌面数字，忽略扑克牌的花色，请按如下规则对这一组扑克牌进行整理：步骤1. 对扑克牌进行分组，形成组合牌，规则如下：当牌面数字相同张数大于等于4时，组合牌为“炸弹”； 3张相同牌面数字 + 2张相同牌面数字，且3张牌与2张牌不相同时，组合牌为“葫芦”； 3张相同牌面数字，组合牌为“三张”； 2张相同牌面数字，组合牌为“对子”； 剩余没有相同的牌，则为“单张”； 步骤2. 对上述组合牌进行由大到小排列，规则如下：不同类型组合牌之间由大到小排列规则：“炸弹” > “葫芦” > “三张” > “对子” > “单张”； 相同类型组合牌之间，除“葫芦”外，按组合牌全部牌面数字加总由大到小排列； “葫芦”则先按3张相同牌面数字加总由大到小排列，3张相同牌面数字加总相同时，再按另外2张牌面数字加总由大到小排列； 由于“葫芦”>“三张”，因此如果能形成更大的组合牌，也可以将“三张”拆分为2张和1张，其中的2张可以和其它“三张”重新组合成“葫芦”，剩下的1张为“单张” 步骤3. ​当存在多个可能组合方案时，按如下规则排序取最大的一个组合方案：依次对组合方案中的组合牌进行大小比较，规则同上； 当组合方案A中的第n个组合牌大于组合方案B中的第n个组合牌时，组合方案A大于组合方案B；
     *
     * 输入描述
     * 第一行为空格分隔的N个正整数，每个整数取值范围[1,13]，N的取值范围[1,1000]
     *
     * 输出描述
     * 经重新排列后的扑克牌数字列表，每个数字以空格分隔
     *
     * @param args
     */
    @Override
    public void ArrangingJoker(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> numbers = new ArrayList<>();
        // 读取输入直到输入结束
        while (sc.hasNext()) {
            numbers.add(sc.nextInt());
        }

        // Step 1: 统计每张卡片的出现次数
        Map<Integer, Integer> count = new HashMap<>();
        for (Integer c : numbers) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        // Step 2: 将卡片按出现次数分组
        Set<Integer> singles = new HashSet<>();
        Set<Integer> pairs = new HashSet<>();
        Set<Integer> triples = new HashSet<>();
        Set<Integer> quads = new HashSet<>();
        // 遍历出现次数统计，分配到相应的集合中
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();
            if (freq == 1) {
                singles.add(num);  // 1次出现的卡片
            } else if (freq == 2) {
                pairs.add(num);    // 2次出现的卡片
            } else if (freq == 3) {
                triples.add(num);  // 3次出现的卡片
            } else {
                quads.add(num);    // 4次出现的卡片
            }
        }

        // Step 3: 创建一个结果列表，存放排序后的卡片
        List<Integer> result = new ArrayList<>();

        // 处理出现次数为4的卡片，按出现次数和卡片值降序排列
        List<Integer> quadsList = new ArrayList<>(quads);

        quadsList.sort((a, b) -> count.get(b) != count.get(a) ? count.get(b) - count.get(a) : b - a);

        for (int q : quadsList) {
            for (int i = 0; i < count.get(q); i++) {
                result.add(q);  // 将出现次数为4的卡片添加到结果中
            }
        }

        // Step 4: 处理出现次数为3的卡片，并尽量与2次的卡片配对
        List<Integer> triplesList = new ArrayList<>(triples);
        List<Integer> pairsList = new ArrayList<>(pairs);
        Collections.sort(triplesList);  // 对出现次数为3的卡片升序排序
        Collections.sort(pairsList);    // 对出现次数为2的卡片升序排序
        while (!triplesList.isEmpty()) {
            int t = triplesList.remove(triplesList.size() - 1);  // 从列表末尾取出3次的卡片
            result.add(t);  // 将3次的卡片添加到结果中
            result.add(t);  // 添加两次
            result.add(t);  // 添加三次
            // 判断是否能和二次的卡片配对，或者如果没有二次卡片则与单次卡片配对
            if (!triplesList.isEmpty() && (pairsList.isEmpty() || triplesList.get(triplesList.size() - 1) > pairsList.get(pairsList.size() - 1))) {
                int leftover = triplesList.remove(triplesList.size() - 1);  // 从3次卡片中移除一个
                singles.add(leftover);  // 将剩余卡片的一个值放入单张卡片的集合中
                result.add(leftover);   // 添加剩余的单张卡片
                result.add(leftover);   // 再添加一次


            } else if (!pairsList.isEmpty()) {
                int p = pairsList.remove(pairsList.size() - 1);  // 从二次卡片中取出一个卡片
                result.add(p);  // 添加到结果中
                result.add(p);  // 再添加一次
            }


        }
        // Step 5: 处理出现次数为2的卡片
        while (!pairsList.isEmpty()) {
            int p = pairsList.remove(pairsList.size() - 1);  // 从二次卡片中取出一个
            result.add(p);  // 添加到结果中
            result.add(p);  // 再添加一次
        }

        // Step 6: 处理出现次数为1的卡片，按降序排列
        List<Integer> singlesList = new ArrayList<>(singles);
        singlesList.sort(Collections.reverseOrder());  // 将单张卡片按降序排列
        result.addAll(singlesList);  // 添
        System.out.println(result.stream().map(String::valueOf).collect(Collectors.joining(" ")));



    }






    /**
     * boss的收入
     * @param args
     */
    @Override
    public   void inComeOfBoss(String args[]){
        Scanner scanner = new Scanner(System.in);
        int lenth = scanner.nextInt();
        int[][] incomes = new int[lenth][3];
        for(int i = 0; i < lenth; i++){
            for(int j = 0; j < 3; j++){
                incomes[i][j]=scanner.nextInt();
            }

        }
        scanner.close();
        //收入
        Map<Integer,Integer> incomeMap = new HashMap<>();
        //关系
        Map<Integer,List<Integer>> relationMap = new HashMap<>();
        for(int i=0;i<incomes.length;i++){
            incomeMap.put(incomes[i][0],incomes[i][2]);
            List<Integer> oldList = relationMap.getOrDefault(incomes[i][1],new ArrayList<>());
            oldList.add(incomes[i][0]);
            relationMap.put(incomes[i][1],oldList);
        }
        //寻找bossId
        Integer bossId=0;
        for(Integer key :relationMap.keySet()){
            if(!incomeMap.containsKey(key)){
                bossId=key;
                break;
            }

        }
        //计算收入
        Integer bossInCome = getInCome(bossId,incomeMap,relationMap);
        System.out.println("bossId="+bossId+",bossInCome="+bossInCome);


    }

    /**
     * 获取bossid
     * @param bossId
     * @return
     */
    private static Integer getInCome(Integer bossId, Map<Integer,Integer> incomeMap , Map<Integer,List<Integer>> relationMap ){
        int inCome = incomeMap.getOrDefault(bossId,0);
        List<Integer> subList = relationMap.getOrDefault(bossId, new ArrayList<>());
        for (int i = 0; i < subList.size(); i++) {
            inCome += getInCome(subList.get(i),incomeMap,relationMap) / 100 * 15;
        }
        return inCome;

    }









    /**
     * 贪心商人
     * @param args
     */
    @Override
    public   void greedyMerchant(String args[]){
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int day = scanner.nextInt();
        int [] holds = new int[num+1];
        int [] prices = new int[day+1];
        for(int i=1;i<=num;i++){
            holds[i] = scanner.nextInt();
        }
        long ans =0;
        for(int i=1;i<=num;i++){
            long res = 0;
            for(int j=1;j<=day;j++){
                prices[j]=scanner.nextInt();
                for(int k=1;k<day;k++){
                    if( prices[j+1]>prices[j]){
                        res+=prices[j+1]-prices[j];
                    }
                }
            }
            ans+=res*holds[i];
        }
        scanner.close();
        System.out.println(ans);
    }



    /**
     * 日志收集
     * @param args
     */
    @Override
    public   void logCollect(String args[]){
        Scanner scanner = new Scanner(System.in);
        List<Integer> logs = new ArrayList<>();
        while (scanner.hasNextLine()){
            logs.add(scanner.nextInt());
        }
        int currNum = 0;
        int maxScore =Integer.MIN_VALUE;
        int totalDelay=0;
        for(int score:logs){
            totalDelay+=currNum;
            currNum+=score;
            if(currNum>=100){
                maxScore = Math.max(maxScore,100-totalDelay);
                break;
            }
            int currScore = currNum-totalDelay;
            maxScore=Math.max(maxScore,currScore);

        }
        System.out.println(maxScore);
        scanner.close();
    }


    /**
     * 分糖果
     * @param args
     */
    @Override
    public   void candyDistribute(String args[]){
        Scanner scanner = new Scanner(System.in);
        Long  candies = scanner.nextLong();
        int step=0;
        while (candies>1){
            if(candies%2==0){
                candies/=2;
            }else{
                if(candies==3||(candies&2)==0){
                    candies--;
                }else{
                    candies++;
                }

            }
            step++;
        }
        System.out.println(step);

    }








}



